C++实现快速排序(Quicksort)算法

 // 快速排序：选第一个对象作为基准，按照该对象的排序码大小，将整个对象 // 序列划分为左右两个字序列： // 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码； // 右侧子序列中所有对象的排序码都大于基准对象的排序码； // 基准对象则排在这两个子序列中间，这也是该对象最终应放的位置 // 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止 #include  // 一次快速排序算法 int quickPass(int arr[], int low, int high) { int down, up, temp; down = low; up = high; temp = arr[low]; while(down <up) { while((down = temp) // 从右向左扫描 up--; if(down <up) arr[down++] = arr[up]; // 在被腾空出来的单元（由down指向）中填入arr[up] while((down <up) && arr[down] <temp) // 从左向右扫描 down++; if(down <up) arr[up--] = arr[down]; // 在被腾空出来的单元（由up指向）中填入arr[down] } arr[down] = temp; // 最后把基准插回到数组中间去 return down; } // 快速排序算法 void quickSort(int arr[], int low, int high) { // 对序列arr[low]到arr[high]作快速排序 int mid; if(low <high) { mid = quickPass(arr, low, high); // 对序列arr[low]到arr[high]作一趟快速排序 quickSort(arr, low, mid-1); // 对左半部分作递归处理 quickSort(arr, mid+1, high); // 对右半部分作递归处理 } } int main(int argc, const char * argv[]) { // insert code here... int len, i;<p style="color:transparent">来源gao!%daima.com搞$代*!码网</p> int arr[] = {40, 30, 60, 90, 70, 10, 20, 40}; len = sizeof(arr) / sizeof(arr[0]); std::cout << "排序前：\n"; for(i = 0; i <len; i++) std::cout << arr[i] << " "; std::cout << std::endl; quickSort(arr, 0, len-1); // 调用快速排序法 std::cout << "排序后：\n"; for(i = 0; i <len; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }

 // 快速排序的另一种方法:只往一边扫描 #include  // 交换两个数 void Exchange(int &a, int &b) { int temp; temp = a; a = b; b = temp; } // 将序列分为左右两部分，左部分较小，右部分较大 int Partition(int arr[], int low, int high) { int x, i, j; x = arr[high]; // 以high位置的数作为基准 i = low - 1; // 进行数据分类：左部分较小，右部分较大 for(j = low; j <high; j++) if(arr[j] <= x) { // 往右扫描找小于或者等于基准的数 i = i + 1; Exchange(arr[i], arr[j]); // 交换 } Exchange(arr[i+1], arr[high]); // 把基准放到中间 return i+1; } // 快速排序算法 void quickSort(int arr[], int low, int high) { int q; if(low <high) { q = Partition(arr, low, high); quickSort(arr, low, q-1); quickSort(arr, q+1, high); } } int main(int argc, const char * argv[]) { int len, i; int arr[] = {40, 30, 60, 90, 70, 10, 20, 40}; len = sizeof(arr) / sizeof(arr[0]); std::cout << "排序前：\n"; for(i = 0; i <len; i++) std::cout << arr[i] << " "; std::cout << std::endl; quickSort(arr, 0, len-1); // 调用快速排序法 std::cout << "排序后：\n"; for(i = 0; i <len; i++) std::cout << arr[i] << " "; std::cout << std::endl; return 0; }