注:以下代码均基于C++
快排算法
思路: 取数组q[]的中间值为参考, 将数组的首尾两端与数组的中间值比较(首端比中间值小, 尾端比中间值大)直至首尾两端均不符合条件.此时再将不符合条件的两个值交换.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| void quickSort(int q[], int l, int r) { if(l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while(i < j) { do i++; while(q[i] < x); do j--; while(q[j] > x); if(i < j) { int t = q[i]; q[i] = q[j]; q[j] = t; } } quickSort(q, l, j), quickSort(q, j + 1, r); }
|
归并排序算法
思路: 将数组q[]从中间分成长度相等的两段, 设其长度中间值为mid. 依次比较q[1]与q[mid + 1]等的大小, 不断将两者其中更小者放入临时数组temp[]中, 直至两段中的一段全部被放入. 此时再将未放完的一段数组全部放入临时数组temp[]中.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void mergeSort(int q[], int l, int r) { if(l >= r) return; int mid = l + r >> 1, i = l, j = mid + 1, t = 0; int temp[100010]; mergeSort(q, l, mid), mergeSort(q, mid + 1, r); while(i <= mid && j <= r) { if(q[i] <= q[j]) temp[t++] = q[i++]; else temp[t++] = q[j++]; } while(i <= mid) temp[t++] = q[i++]; while(j <= r) temp[t++] = q[j++]; for(i = l, t = 0;i <= r;i++, t++) q[i] = temp[t]; }
|
更新中…