[算法系列之五]快速排序

ゝ一世哀愁。 2023-05-31 15:23 8阅读 0赞

### 【分析】 ###

![20140503142205281][]

### 【伪代码】 ###

![20140503142214281][]

![20140503142234312][]

### **【思路图】**  ###

![Center][]

### 【运行过程】  ###

![20140503142651781][]

![20140503142704375][]

### 【代码】 ###

/*********************************
    *   日期：2014-04-01
    *   作者：SJF0115
    *   题目：快速排序
    **********************************/
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    //对子数组array[p...r]就地重排
    int Partition(int array[],int p,int r){
        int j,temp;
        //定义哨兵
        int x = array[r];
        //i为小于哨兵元素的最后一个元素下标
        int i = p - 1;
        //j为待排序元素的第一个元素
        for(j = p;j < r;j++){
            //跟哨兵比较
            if(array[j] < x){
                i++;
                //交换array[i] array[j]
                temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }
        //交换array[i+1](大于哨兵元素的第一个元素) array[r]
        temp = array[i+1];
        array[i+1] = array[r];
        array[r] = temp;
        //返回分割下标
        return i + 1;
    }
    //快排
    void QuickSort(int array[],int p,int r){
        if(p >= r || array == NULL){
            return;
        }
        int index = Partition(array,p,r);
        QuickSort(array,p,index-1);
        QuickSort(array,index+1,r);
    }
     
    int main()
    {
        int array[] = {2,8,7,1,3,5,6,4};
        QuickSort(array,0,7);
        for(int i = 0;i <= 7;i++){
            printf("%d\n",array[i]);
        }
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/24916745][https_blog.csdn.net_SunnyYoona_article_details_24916745]

[20140503142205281]: /images/20230531/8496c1ffa8e743a3aab5714451f87956.png
[20140503142214281]: /images/20230531/dbbb99b061a441e2bce554eca193b8f9.png
[20140503142234312]: /images/20230531/06f3a918573b4ec891aa530931015f61.png
[Center]: /images/20230531/f6537b1025334577bc7f23617bb2b4cb.png
[20140503142651781]: /images/20230531/e8cf4c70749f40f7a2c9a9313b4a1f93.png
[20140503142704375]: /images/20230531/73997510d4be4160953ecf25f734a597.png
[https_blog.csdn.net_SunnyYoona_article_details_24916745]: https://blog.csdn.net/SunnyYoona/article/details/24916745