C++快排
3678 点击·0 回帖
灯火互联
楼主
 |  | |
 | 最近在看算法导论，就实现了一些简单的算法！
核心是分治 首先先完成交换两个值的函数， 然后完成分割操作 最后确定递归条件！ [cpp] int exchange(int A[],int i,int j) { int temp = A; A = A[j]; A[j] = temp; return 0; } int Partion(int A[],int p,int r) { int x= A[r]; int i = p-1; for (int j = p; j < r; j++) { if (A[j]<=x) { i = i+1; exchange(A,i,j); } } exchange(A,i+1,r); return i+1; } void QuickSort(int A[],int p,int r) { if (p<r-1) { int q = Partion(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } int exchange(int A[],int i,int j) { int temp = A; A = A[j]; A[j] = temp; return 0; } int Partion(int A[],int p,int r) { int x= A[r]; int i = p-1; for (int j = p; j < r; j++) { if (A[j]<=x) { i = i+1; exchange(A,i,j); } } exchange(A,i+1,r); return i+1; } void QuickSort(int A[],int p,int r) { if (p<r-1) { int q = Partion(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } 测试快排的代码： [cpp] int A[10]={2,3,4,5,6,7,8,9,0,1}; QuickSort(A,0,9); for (int i = 0; i <10; i++) { cout<<A<<"\t"; } cout <<endl; int A[10]={2,3,4,5,6,7,8,9,0,1}; QuickSort(A,0,9); for (int i = 0; i <10; i++) { cout<<A<<"\t"; } cout <<endl; | |
 |  |