代碼

挖坑法

解釋

1. 選取一個關(guān)鍵字(key)作為樞軸，一般取整組記錄的第一個數(shù)/最后一個，這里采用選取序列第一個數(shù)為樞軸，也是初始的坑位。
2. 設(shè)置兩個變量i = l;j = r;其中l(wèi) = 0, r = n - 1;
3. 從j一直向前走，直到找到一個小于pivot的值，然后將該數(shù)放入坑中，坑位變成了array[j]。
4. i一直向后走，直到找到一個大于pivot的值，然后將該數(shù)放入坑中，坑位變成了array[i]。
5. 重復(fù)3和4的步驟，直到left和right相遇，然后將pivot放入最后一個坑位。

當(dāng)left >= right時，將key放入最后一個坑，就完成了一次排序。
注意，left走的時候right是不動的，反之亦然。因為right先走，所有最后一個坑肯定在array[left]。

#include <iostream>void quick_sort(int s[], int l, int r)
{if (l < r){int i = l, j = r, pivot = s[l];while (i < j){while (i < j && s[j] >= pivot){j--;}s[i] = s[j];while (i < j && s[i] <= pivot){i++;}s[j] = s[i];}s[i] = pivot;quick_sort(s, l, i - 1);quick_sort(s, i + 1, r);}
}int main(int argc, char* argv[]) {int n;scanf("%d", &n);int *s = (int *)malloc(n * sizeof(int));for (int i  = 0; i < n; i++){scanf("%d", &s[i]);}quick_sort(s, 0, n - 1);for (int i = 0; i <n; i++){printf("%d ", s[i]);}printf("\n");return 0;
}

非遞歸

int partition(int *a, int left, int right)
{int pivot = a[left];while (left < right){while (left < right && a[right] >= pivot)right--;a[left] = a[right];while (left < right && a[left] <= pivot)left++;a[right] = a[left];}a[left] = pivot;return left;
}void q_sort_stack(int *a, int n)
{int left = 0;int right = n - 1;stack<int> s;s.push(left);s.push(right);while(!s.empty()){right = s.top();s.pop();left = s.top();s.pop();int index = partition(a, left, right);if (index - 1 > left){s.push(left);s.push(index - 1);}if (index + 1 < right){s.push(index + 1);s.push(right);}}
}

一個要注意的問題

C語言如何計算數(shù)組的長度

32位與64位下各類型長度對比

當(dāng)我計算數(shù)組長度時候，要在傳函數(shù)之前計算，而不是在傳完函數(shù)之后再計算
64位系統(tǒng)下一個整形指針變量長度是8，而在32位系統(tǒng)下是4

參考鏈接

https://blog.csdn.net/qq_36528114/article/details/78667034#commentBox

總結(jié)

以上是生活随笔為你收集整理的快速排序的递归和非递归实现 c语言版本的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。