|
快速排序的三个步骤： 1、分解：将数组A[l...r]划分成两个（可能空）子数组A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每个元素都小于等于A(p)，而且，小于等于A[p+1...r]中的元素。下标p也在这个划分过程中计算。 2、解决：通过递归调用快速排序，对数组A[l...p-1]和A[p+1...r]排序。 3、合并：因为两个子数组时就地排序，将它们的合并并不需要操作，整个数组A[l..r]已经排序。
1.快速排序的基础实现： QUICKSORT(A, l, r) if l < r then q = PARTION(A, l, r) QUICKSORT(A, l, p-1) QUICKSORT(A, p+1, r) 两路PARTION算法主要思想： move from left to find an element that is not less move from right to find an element that is not greater stop if pointers have crossed exchange
实现代码： [cpp] view plaincopy 1. int partition(double* a, int left, int right) 2. { 3. double x = a[right]; 4. int i = left-1, j = right; 5. for (;;) 6. { 7. while(a[++i] < x) { } 8. while(a[--j] > x) { if(j==left) break;} 9. if(i < j) 10. swap(a[i], a[j]); 11. else break; 12. } 13. swap(a[i],a[right]); 14. return i; 15. } 16. 17. void quickSort1(double* a, int left, int right) 18. { 19. if (left 20. { 21. int p = partition(a, left, right); 22. 23. quickSort1(a, left, p-1); 24. quickSort1(a, p+1, right); 25. } 26. }
2.非递归算法：其实就是手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈。 实现代码： [cpp] view plaincopy 1. void quickSort2(double* a, int left, int right) 2. { 3. stack<int> t; 4. if(left 5. { 6. int p = partition(a, left, right); 7. 8. if (p-1>left) 9. { 10. t.push(left); 11. t.push(p-1); 12. } 13. if (p+1 14. { 15. t.push(p+1); 16. t.push(right); 17. } 18. 19. while(!t.empty()) 20. { 21. int r = t.top(); 22. t.pop(); 23. int l = t.top(); 24. t.pop(); 25. 26. p = partition(a, l, r); 27. 28. if (p-1>l) 29. { 30. t.push(l); 31. t.push(p-1); 32. } 33. if (p+1 34. { 35. t.push(p+1); 36. t.push(r); 37. } 38. 39. } 40. } 41. }
3.三路划分快速排序算法：
实现代码： [cpp] view plaincopy 1. void quickSort3Way(double a[], int left, int right) 2. { 3. if(left < right) 4. { 5. double x = a[right]; 6. int i = left-1, j = right, p = left-1, q = right; 7. for (;;) 8. { 9. while (a[++i] < x) {} 10. while (a[--j] > x) {if(j==left) break;} 11. if(i < j) 12. { 13. swap(a[i], a[j]); 14. if (a[i] == x) {p++; swap(a[p], a[i]);} 15. if (a[j] == x) {q--; swap(a[q], a[j]);} 16. } 17. else break; 18. } 19. swap(a[i], a[right]); j = i-1; i=i+1; 20. for (int k=left; k<=p; k++, j--) swap(a[k], a[j]); 21. for (int k=right-1; k>=q; k--, i++) swap(a[i], a[k]); 22. 23. quickSort3Way(a, left, j); 24. quickSort3Way(a, i, right); 25. } 26. }
4.测试代码： [cpp] view plaincopy 1. #include 2. #include 3. #include 4. using namespace std; 5. 6. // 产生（a,b）范围内的num个随机数 7. double* CreateRand(double a, double b, int num) 8. { 9. double *c; 10. c = new double[num]; 11. srand((unsigned int)time(NULL)); 12. for (int i=0; i 13. c[i] = (b-a)*(double)rand()/RAND_MAX + a; 14. return c; 15. } 16. 17. // 两路划分，获取中轴，轴左边数小于轴，轴右边数大于轴 18. double partition(double* a, int left, int right) 19. { 20. ... 21. } 22. 23. // 1.递归快速排序，利用两路划分 24. void quickSort1(double* a, int left, int right) 25. { 26. ... 27. } 28. 29. // 2.非递归快速排序，手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈 30. void quickSort2(double* a, int left, int right) 31. { 32. ... 33. } 34. 35. // 3.利用三路划分实现递归快速排序 36. void quickSort3Way(double a[], int left, int right) 37. { 38. ... 39. } 40. 41. void main() 42. { 43. double *a, *b, *c; 44. int k=10000000; 45. time_t start,end; 46. 47. a = CreateRand(0,1,k); 48. b = CreateRand(0,1,k); 49. c = CreateRand(0,1,k); 50. 51. start = clock(); 52. quickSort1(a,0,k-1); 53. end = clock(); 54. cout<<"1.recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"< 55. 56. start = clock(); 57. quickSort2(b,0,k-1); 58. end = clock(); 59. cout<<"2.non-recursive "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"< 60. 61. start = clock(); 62. quickSort3Way(c,0,k-1); 63. end = clock(); 64. cout<<"3.3 way "<<1.0*(end-start)/CLOCKS_PER_SEC<<" seconds"< 65. 66. cout< 67. system("pause"); 68. }
1.recursive 1.951 seconds 2.non-recursive 2.224 seconds 3.3 way 1.677 seconds 结果可以看出非递归算法由于需要手动进行算法过程中的变量保存，执行效率低于递归算法；3路划分算法利用少量多余的交换减少了快排的复杂度，执行效率高于传统2路快排算法。
|
|
|
来自： kingwenguang > 《排序》
