排序（算法）

1.快速排序

递归分治的思想

每一次都选择一个值，将小于该值的数字放到一边，将大于该值的数字放到一边

1分为2，2分为4的方法不断向下延伸，将范围一次次缩小进行排序

quick_sort(int a[],int l,int r) { if(l >= r) return; //退出机制 int i = l - 1,j = r + 1,x = a[l + r >> 1]; while(i < j) { do i++ ;while(a[i] < x); do j-- ;while(a[j] > x); if(i < j) swap(a[i],a[j]); } quick_sort(a,l,j); quick_sort(a,j + 1,r); }

2.归并排序

递归的思想

merge_sort(int q[],int l,int r) { if(l >= r) return; int mid = l + r >> 1; merge_sort(q,l,mid),merge_sort(q,mid + 1,r); int k = 0;i = l,j = mid + 1; while(i <= mid && j <= r) if(q[i] <= q[j]) tmp[k ++] = q[i ++]; else tmp[k ++] = q[j ++]; while(i <= mid) tmp[k ++] = q[i ++]; while(j <= r) tmp[k++] = q[j ++]; for(i = l,j = 0;i <= r;i++, j++) q[i] = tmp[j]; }