有两个版本，主要是Partition的思路不同，分别实现： 1. 《算法导论》的版本： 就是Partition时，比较的时候，主元的位置不变，只是在前面扫过一次，把比主元大的放在后面，比主元小的放在前面。这样的复杂度一看很明显就是 O(nlog(n))
int Partition(int* a, int low, int high) { int pivot = a[high]; int i = low - 1; //大的不动，小的交换 for (int j = low; j < high; j++) { if (a[j] > pivot) { //pass } else { i ++; swap(a[i], a[j]); } } swap(a[i + 1], a[high]); return i+1; } void QuickSort(int* a, int low, int high) { if (low >= high) return; int mid = Partition(a, low, high); QuickSort(a, low, mid - 1); QuickSort(a, mid + 1, high); } 数据结构课上老师讲的版本： Partition的时候，主元的位置在不停变动，从最后面逐渐移动到中间，这种版本要注意算法停止的边界条件 int Partition_1(int* a, int low, int high) { int pivot = high; int index = low; while(1) { if (pivot > index) { if (a[pivot] < a[index]) { swap(a[pivot], a[index]); swap(pivot, index); index --; } else { index ++; } } else if (pivot < index) { if (a[pivot] > a[index]) { swap(a[pivot], a[index]); swap(pivot, index); index ++; } else { index --; } } else break; } return pivot; }