相对于前面我们了解了归并排序发算法，其分为迭代法和递归法。
那么这次来了解下快速排序，快速排序也分为迭代法和递归法。
那么今天的主角是迭代法。同样是迭代法，快速排序的迭代法可以说是比归并排序的迭代法要容易懂的多了。
快速排序
在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
过程演示：
那么迭代法其实现如：
#include
typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort(int arr[], const int len) {
if (len
return; // 避免len等於負值時引發段錯誤（Segment Fault）
// r[]模擬列表(數組類型的結構躰)
Range r[len];
int p = 0;
//最初的排序範圍
r[p] = new_Range(0, len - 1);
p=p+1;
while (p) {
p=p-1;
//每次獲取上一個排序範圍
Range range = r[p];
if (range.start >= range.end){
continue;
}
// 選取中間點為基準點
int mindex=(range.start + range.end) / 2;
int mid = arr[mindex];
int left = range.start, right = range.end;
printf(" 左索引:%d,中索引:%d,右索引:%d ",left,mindex,right);
printf(" 左值:%d,中值:%d,右值:%d ",arr[left],mid,arr[right]);
printf(" 左範圍:");
for(int z=left;z
if(z==mindex-1){
printf("%d",arr[z]);
}
else{
printf("%d,",arr[z]);
}
}
printf(" ");
printf(" ");
printf("左到右：");
for(int zy=left;zy
if(zy==right){
printf("%d",arr[zy]);
}
else{
printf("%d,",arr[zy]);
}
}
printf(" 右範圍：");
for(int y=mindex+1;y
if(y==right){
printf("%d",arr[y]);
}
else{
printf("%d,",arr[y]);
}
}
printf(" ");
printf(" ");
printf(" ");
do
{
printf(" %-8s left:%d,right:%d","",left,right);
// 檢測基準點左側是否符合要求
//循環1：遍歷當前隊列，從左到右，檢查每個小于中間值的值對應的索引
while (arr[left] < mid) {
printf(" %-8s 檢查左側基准:%d小于%d,left加1=%d","",arr[left],mid,left+1);
//++left;
left=left+1;
}
//循環2：遍歷當前隊列，從右向左，檢查每個大于中間值的值對應的索引
while (arr[right] > mid){
//--right;
printf(" %-8s 檢查右側基准:%d大于%d,right減1=%d","",arr[right],mid,right-1);
right=right-1;
}
/*
由于循環1的終止條件，則循環1結束后（即便循環1，一次都沒有執行過），left對應的值一定大于等于中間值
同理，此時循環2（無論執行還是沒有執行），那麽right對應的值一定小于等于中間值
那麽此時對于索引left和right而言，left若小于right，那麽豈不是左邊的值小于右邊的值，這樣不就是反了，所以下面要進行交換
*/
if (left
{
printf(" %-8s left(%d)小于等于right(%d)準備交換 ","",left,right);
printf(" %-8s 交換前arr整體隊列：","");
for(int jh=0;jh
if(jh==len-1){
printf("%d",arr[jh]);
}
else{
printf("%d,",arr[jh]);
}
}
printf(" %-8s 交換前的左右值：left:arr[%d]=%d,right:arr[%d]=%d","",left,arr[left],right,arr[right]);
printf(" ");
printf(" %-8s 交換前的左值：arr[%d]=%d","",left,arr[left]);
swap(&arr[left],&arr[right]);
printf(" %-8s 交換后的左值：arr[%d]=%d","",left,arr[left]);
printf(" %-8s 交換后arr整體隊列：","");
for(int jh=0;jh
if(jh==len-1){
printf("%d",arr[jh]);
}
else{
printf("%d,",arr[jh]);
}
}
printf(" ");
// 移動指針以繼續
/*
交換以後也未必就能保證隊列從左到右邊是從小到大自增的
例如：
8，7,1，5，2
這裏中間值假比如為1，那麽8比2大，則交換之後就是：
2,7,1,5,8
但是2,7,1,5,8中
7又比5大，所以兩邊都需要向中間值進一步進行再次比較
*/
left=left+1;
right=right-1;
printf(" %-8s 下一個左右 left:%d,right:%d ","",left,right);
}
}
/*
如果左邊索引還是小于右邊索引，則表示，從左向右與從右向左這兩個指針還沒有碰面
*/
while (left
/*
上面的do循環是進行某個子序列中進行交換比較的
那麽儅right還大于上個序列（有可能是原始序列，也有可能是原始序列被中分n次后的某個子序列（中分的叫法可能不太合適，準確的來説就是從兩邊向中間推n次之後的剩餘空間的序列））的開始位置
則説明還有剩餘的局部序列還沒有被比較到
*/
if (range.start < right) {
r[p] = new_Range(range.start, right);
p=p+1;
}
//這個和range.start < right是同理，上面是從右邊看向左邊的角度是，這個是從左邊看向右邊的角度。想想其它情況下則都是原始序列就到此爲止全部排序完成了
if (range.end > left){
r[p] = new_Range(left, range.end);
p=p+1;
}
}
}
void main(){
int arr[]=;
int len=9;
quick_sort(arr,len);
for(int x=0;x
printf("%d ",arr[x]);
}
}