快速排序1

基本思想：

1. 从序列当中选择一个基准数(pivot),我们选择第一个数为基准数。 2. 先设置一个哨兵j,从右向左找到比基准数小的数 3. 再设置一个哨兵i,从左往右找到比基准数大的数(i不能大于j) 4. 如果i<j,则将两个哨兵所在位置的数值交换 5. 当两个哨兵相遇时,将哨兵i所在的数值与基准数(也就是第一个数)交换 6. 此时整个数组变成的三部分(比基准数小的左边部分,中间部分的基准数,比基准数大的右边部分) 7. 递归排列基准数左边部分与基准数右边部分

代码

#include <stdio.h>void _quick_sort(int arr[],int l,int r){if(l>=r){return;}int p = arr[l];//设置基准数int i = l;int j = r;while (i!=j) {//顺序很重要，从右向左找while (arr[j]>=p&&j>i) {j--;}//再从左往右找while (arr[i]<=p&&i<j) {i++;}//交换两个数的位置if (i<j) {//当哨兵i和哨兵j没有相遇时int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}arr[l] = arr[i];arr[i] = p;_quick_sort(arr, l, i-1);//继续处理左边的，这里是一个递归的过程_quick_sort(arr, i+1, r);//继续处理右边的，这里是一个递归的过程 }int quick_sort(int arr[],int n){_quick_sort(arr,0,n-1);return 0; }int main(int argc, const char * argv[]) {// insert code here...int arr[] = {9,2,1,6,5,4,3};quick_sort(arr, 7);for (int i = 0; i<7; i++) {printf("%d\n",arr[i]);}return 0; }

以下图片及内容来源来之图书啊哈!算法

类似下面这种排序

6 1 2 5 4 3 9 7 10 8

方法很简单:分别从初始序列"6 1 2 7 9 3 4 5 10 8"两端开始探测。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列的最左边和最右边，我们为这两个变量起一个好听的名字，分别叫做"哨兵i"和"哨兵j"。

首先哨兵j开始出动。因为此处设置的基准数的最左边的数，所以需要让哨兵j先出动，这一点非常重要(请自己想一想为什么)。哨兵j一步一步往左挪动(即j--)，直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++)，直到找到一个大于6的数停下来。

现在交换哨兵i和哨兵j所指向的元素的值。

继续移动

交换

相遇

与基准数交换

转载于:https://www.cnblogs.com/zheng-chuang/p/6858591.html

总结

以上是生活随笔为你收集整理的快速排序1的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。