本文主要是三大常用排序的实现，包括快速排序的递归方法，循环方法。归并排序的递归方法，循环方法。以及堆排序。
快速排序：
递归实现（快排）
void Show(int ar[],int len) { copy(ar,ar+len,ostream_iterator<int>(cout," ")); cout<<endl; } //快速排序--递归 int Quick_sort_once(int ar[],int left,int right) { int tmp = ar[left]; while(left < right) { while(left < right && tmp <= ar[right]) right--; if(left < right) ar[left] = ar[right]; while(left < right && tmp >= ar[left]) left++; if(left < right) ar[right] = ar[left]; } ar[left] = tmp; return left; } void Quick_sort(int ar[],int left,int right) { if(left < right) { int mid = Quick_sort_once(ar,left,right); Quick_sort(ar,left,mid-1); Quick_sort(ar,mid+1,right); } } void Quick_sort(int ar[],int len) { if(ar == NULL || len <= 0) return ; Quick_sort(ar,0,len-1);//递归 } void main() { int ar[] = {3,6,8,2,4,1,0,9,5}; int len = sizeof(ar)/sizeof(ar[0]); Quick_sort(ar,len); Show(ar,len); } 循环实现（快排） int Quick_sort_once(int ar[],int left,int right) { int tmp = ar[left]; while(left < right) { while(left < right && tmp <= ar[right]) right--; if(left < right) ar[left] = ar[right]; while(left < right && tmp >= ar[left]) left++; if(left < right) ar[right] = ar[left]; } ar[left] = tmp; return left; } void Quick_sort_while(int ar[],int left,int right) { int *br = new int[(right+1)*2]; if(br != NULL) { int count = 0; br[count++] = left; br[count++] = right; while(count > 0) { int low = br[count-2]; int high = br[count-1]; if(low < high) { int mid = Quick_sort_once(ar,low,high); count -= 2; br[count++] = low; br[count++] = mid-1; br[count++] = mid+1; br[count++] = high; } else count -= 2; } } delete []br; } void Quick_sort(int ar[],int len) { if(ar == NULL || len <= 0) return ; Quick_sort_while(ar,0,len-1);//循环 }void main(){ int ar[] = {3,6,8,2,4,1,0,9,5}; int len = sizeof(ar)/sizeof(ar[0]); Quick_sort(ar,len); Show(ar,len);} 归并排序递归实现（归并）
void Merge_sort_once(int ar[],int br[],int low1,int high1,int low2,int high2) { int k = low1; int m = k; while(low1 <= high1 && low2 <= high2) { if(ar[low1] <= ar[low2]) br[k++] = ar[low1++]; else br[k++] = ar[low2++]; } while(low1 <= high1) br[k++] = ar[low1++]; while(low2 <= high2) br[k++] = ar[low2++]; k--; while(k >= m) ar[k] = br[k--]; } void Merge_sort(int ar[],int br[],int left,int right) { if(left < right) { int mid = left + (right - left) / 2; Merge_sort(ar,br,left,mid); Merge_sort(ar,br,mid+1,right); Merge_sort_once(ar,br,left,mid,mid+1,right); } } void Merge_sort(int ar[],int len) { if(ar == NULL || len <= 0) return ; int *br = new int[len+1]; Merge_sort(ar,br,0,len-1); } void main() { int ar[] = {3,6,8,2,4,1,0,9,5}; int len = sizeof(ar)/sizeof(ar[0]); Merge_sort(ar,len); Show(ar,len); } 循环实现（归并）void Merge_sort_once(int ar[],int br[],int len,int gap) { int low1 = 0; int high1 = low1+gap-1; int low2 = high1+1; int high2 = low2+gap-1 > len ? len : low2+gap-1; int k = 0; while(low2 <= len) { while(low1 <= high1 && low2 <= high2) { if(ar[low1] <= ar[low2]) br[k++] = ar[low1++]; else br[k++] = ar[low2++]; } while(low1 <= high1) br[k++] = ar[low1++]; while(low2 <= high2) br[k++] = ar[low2++]; low1 = high2+1; high1 = low1+gap-1; low2 = high1+1; high2 = low2+gap-1 > len ? len : low2+gap-1; } while(low1 <= len) br[k++] = ar[low1++]; k--; while(k >= 0) { ar[k] = br[k--]; } } void Merge_sort_while(int ar[],int left,int right) { int *br = new int[right+1]; for(int i = 1; i < right+1; i *= 2) { Merge_sort_once(ar,br,right,i); } delete []br; }void Merge_sort(int ar[],int len) { if(ar == NULL || len <= 0) return ; Merge_sort_while(ar,0,len-1); } void main() { int ar[] = {3,6,8,2,4,1,0,9,5}; int len = sizeof(ar)/sizeof(ar[0]); Merge_sort(ar,len); Show(ar,len); }
堆排序
void Adjust(int ar[],int k,int len) { int tmp = ar[k]; int i = k*2+1; while(i < len) { if(i + 1 < len && ar[i] < ar[i+1]) { i++; } if(ar[i] > tmp) { ar[k] = ar[i]; k = i; i = k*2+1; } else break; } ar[k] = tmp; } void Heap_sort(int ar[],int len) { if(ar == NULL || len <= 0) return ; int i = (len-1-1)/2; while(i >= 0) { Adjust(ar,i,len); i--; } for(int k = len-1; k > 0; --k) { int tmp = ar[0]; ar[0] = ar[k]; ar[k] = tmp; Adjust(ar,0,k); } } void main() { int ar[] = {3,6,8,2,4,1,0,9,5}; int len = sizeof(ar)/sizeof(ar[0]); Heap_sort(ar,len); Show(ar,len); }
