快速排序

2021-01-30

字数统计: 786字 | 阅读时长≈ 3分

快速排序

代码

大概的思路是找到一个基点，然后遍历整个数组（C语言为例），使用左右两个索引然后，没有重合的时候找到前面比基点大的，后面比基点小的，之后进行交换，保证前面的都比基点小，后面的都比基点大，然后当i>j时把基点和i的索引位置的数字交换，之后进行递归调用即可

PS：快速排序不稳定
举个例子：待排序数组: int a[] ={1, 2, 2, 3, 4, 5, 6};在快速排序的随机选择比较子(即pivot)阶段：若选择a[2]（即数组中的第二个2）为比较子，，而把大于等于比较子的数均放置在大数数组中，则a[1]（即数组中的第一个2）会到pivot的右边，那么数组中的两个2非原序（这就是“不稳定”）。若选择a[1]为比较子，而把小于等于比较子的数均放置在小数数组中，则数组中的两个2顺序也非原序

#include <iostream>
using namespace std;
void Sort(int *a,int low,int high);
int part(int *a,int low,int high);
void swap_fun(int *a,int *b);
int main()
{
    int a[]={29,20,25,12,45,98,26,84,25,47,46,48,646,26,6546,486,516};
    int lth=sizeof(a)/sizeof(a[0]);//获取当前数组的长度
    Sort(a,0,lth-1);
    //传入参数，这里注意传入数组的下标问题，就C/C++/java等都是从O开始的
    //记住后面的都是这样
    for(int i=0;i<=lth-1;i++){
        cout<<a[i]<<endl;
    }
    system("pause");
    return 0;
}
int part(int *a,int low,int high)
{
    /*PS：++i和i++，前者先加一，所以开始要减一
     * i代表着数组右边的指针，相当于索引；j代表着数组右边的指针，同理也是索引
     * 前面找比基点大的，后面找比基点小的，找到后两个位置进行交换即可
     * 最后记得把基点进行相关的交换问题
     * 如果最后i比j大那么前面都是比基点小的，后面都是大的，此时记住把基点和i的索引进行交换
     * 因为此时i>j,换了之后，继续递归调用就可以了
     */
    int i=low-1;
    int j=high;
    int p=a[high];//此处以最右边为基点
    while(1)
    {
        //这里的用法是不停的往后面移动，不停的判断，如果满足就进行相关的交换
        while(a[++i]<p);
        while(a[--j]>p);
        if(i<j)
        {
            swap_fun(&a[i],&a[j]);
        }
        else
        {
            break;//程序已经结束了，直接退出循环
        }    
    }
    swap_fun(&a[i],&a[high]);
    return i;
}
void Sort(int *a,int low,int high)
{
    if(low<high)
    //不停的循环，从part函数中找到一次，然后进行不停的递归调用，之后进行左右再次进行分离
    //关键是一次的分离函数
    {
        int mid=part(a,low,high);
        Sort(a,low,mid-1);
        Sort(a,mid+1,high);
    }
}
void swap_fun(int *a,int *b)
{//简单的交换函数
    int temp=*a;
    *a=*b;
    *b=temp;
}

本文作者： windfill
本文链接： https://windfill.github.io/article/ff8068c0.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！