二、相关代码

int partition(int* arr, int n) {int key = arr[0];int i=1;int j=n-1;while(iwhile(i=j) break;while(iarr[i]) ++i;if(i>=j) break;SWAP(arr[i], arr[j]);++i;--j;}if(key > arr[i]) {return i;}else {return i-1;}
}void quick_sort(int* arr, int n) {if(n<=1) return;int p = partition2(arr, n);SWAP(arr[0], arr[p]);quick_sort(arr, p);quick_sort(arr+p+1, n-p-1);
}

小细节改进

版本一

由于我们在最初的版本里面设置了的i=1，两者在比较的过程中设置每次在交换之后，移动i, j，但这使得在返回下表的时候还要对flag和a[i]进行比较，但事实上，我们可以直接让两个下表自己跑，满足条件则交换，具体如下：

int partition1(int* arr, int n) {int key = arr[0];int i = 0, j = n-1;while(i < j) {while(i= arr[i])  ++i;SWAP(arr[i], arr[j]);}arr[i] = key;return i;}
void quick_sort(int* arr, int n) {if(n<=1) return;int p = partition2(arr, n);quick_sort(arr, p);quick_sort(arr+p+1, n-p-1);
}

版本二

我们将数组中的第一个元素存在了key里面，那么此时arr[0]可以作为交换两个数的中间变量，具体实现如下：

int partition2(int* arr, int n) {int key = arr[0];int i=0, j=n-1;while(i < j) {while(i= arr[i]) ++i;arr[j] = arr[i];}arr[i] = key;return i;
}void quick_sort(int* arr, int n) {if(n<=1) return;int p = partition2(arr, n);quick_sort(arr, p);quick_sort(arr+p+1, n-p-1);
}