c++中快速排序_c++ 快速排序

引言

快速排序一直是排序算法中使用比较高频的一种算法。下面简述一下快排，予以记录。

实现思想

在一组无序的数组中，定义一个标志flag，这里以数组中左起第一个元素作为标志，定义一个i值和j值，分别表示从左边开始与flag比较的数组元素下标，从右边开始与flag比较的数组元素下标，这里需要注意的是，若选择数组中左起第一个元素为flag,则先从右开始与flag比较，反之亦然。当下标j 和下标i的元素相同的情况下，停止此次排序，用flag与当前下标i(下标i和下标j相等)的元素进行交换，就能满足左边小于flag的值，右边大于flag的值。然后以左边的元素构成一个数组，依旧选择左起第一个元素为flag,同时下标i为左起第一个元素的下标，下标j为数组的右侧最后一个元素的下标，开始比较排序，类似之前的操作。下面举例说明。
23，54，6，34，55，12，4，67，8，29
上面的数组中，选择左起第一个元素 23作为flag,定义i和j作为下标，分别指向最左边和最右边，即i指向23，j指向29，现在进行第一轮排序，要求左边的元素小于等于23，右边的元素大于等于23。29大于23，满足要求，j–,此时j指向元素8，8<23不满足右边的元素大于flag,停止右边的移动比较，开始比较左边i下标的元素，23等于23，满足条件，开始下一位54，54>23,不满足条件，这时交换54与8的值，交换后数组元素的值为：
23，8，6，34，55，12，4，67，54，29
接下来进行第二次排序。此时经过上一次的排序后，下标i处的元素是8，下标j处的元素为54,接着j–,j处的元素为67，67>23满足条件，j–,下标j处的元素为4，4<23不满足条件，停止右侧的比较，开始左侧的比较，左侧下标i处的元素为8，满足条件，i++，下标i处的元素为6，6<23满足条件，i++,下标i处的元素为34，34>23不满足条件，交换下标i处是元素34与下标j处的元素4，交换后数组的元素为：
23，8，6，4，55，12，34，67，54，29
接着比较右边j下标处的元素，34>23满足条件，j–,下标j处的元素为12，12<23不满足条件，左边下标i处的元素为4，4<23满足条件，i++,下标i处的元素为55，55>23不满足条件，交换下标i处的元素55与下标j处的元素12，交换后数组的元素为：
23，8，6，4，12，55，34，67，54，29
接着比较右侧下标j处的元素55，55>23满足条件，j–,下标j处的元素为12，12<23不满足条件，停止右侧下标j的元素比较，此时左侧的元素下标i 和右侧的元素下标j都为同一个元素的下标，这时用flag与下标为i的元素进行交换，交换后元素的值为：
12，8，6，4，23，55，34，67，54，29
这样完成了第一轮排序，实现了23左侧比23小，右侧比23大。下面以23左侧的元素构成一个数组：
”12，8，6，4“
依旧选取12为flag,下标i处的元素为12，下标j处的元素为4，从右侧开始比较，4<12,不满足条件，停止下标j处的元素比较，开始下标i处的元素比较，12=12满足条件，i++,下标i处的元素为8，8 <12满足条件，i++,下标i处的元素为6，6<!2满足条件，i++，下标i处的元素为4，此时下标i处的元素和下标j处的元素是同一个元素，停止下标i的比较，用flag与下标i处的元素4交换位置，交换后的数组：
”4，8，6，12“
此时12以左的元素小于12，这时以12以左的元素构成一个数组，
”4，8，6“
左起第一个元素4为flag,下标i处的元素为4，下标j处的元素为6，开始右侧的元素比较，6 >4满足条件，j–,下标j处的元素为8，8>4满足条件，j–，下标j处的元素为4，此时下标i处的元素和下标j处的元素相等，交换flag与下标i处的元素，flag和下标i处的元素为同一个元素，此时，4右侧的元素比4大，以右侧的元素组成一个数组，
”8，6“
同理，flag为8，下标i处的元素为8，下标j处的元素为6，开始右侧的比较，6<8不满足条件，开始左侧的比较，下标i处的元素为8，8==8满足条件，i++，下标i处的元素为6，此时下标i和下标j为同一个元素的下标，交换flag和下标i的元素，交换后数组：
“6,8”
8左侧比8小，此时在最开始以第一个元素23为标志得到的左侧的数组为：
”4，6，8，12“
23右侧的数组：
”55，34，67，54，29*
同理以第一个元素55为flag,下标i处的元素为55，下标j处的元素为29，开始右侧的比较，29<55不满足条件，开始左侧的比较,下标i处的元素55，55等于55，i++，下标i处的元素为34，34<55满足条件，i++,下标i处的元素为67，67>55不满足条件，交换下标i和下标j处的元素，得到数组：
“55，34，29，54，67”
此时下标j处的元素为67，67 >55,满足条件，j–，下标j处的元素为54，54<55不满足条件，下标i处的元素为29，29<55满足条件，i++，下标i处的坐标为54，下标i和下标j处的元素为同一个元素，交换flag与下标i处的元素得到数组：
“54，34，29，55，67”
这时55右侧比55大，左侧元素比55小，以左侧元素构成数组：
“54，34，29”
第一个元素54为flag,下标i为54的下标，下标j为数组的右侧最后一个元素的下标，开始右侧的比较，下标j处的元素29<54不满足条件，下标i处的元素54等于54，i++，下标i处的元素为34，34<54满足条件，i++,下标i处的元素为29，下标i处的元素与下标j处的元素为同一个元素，交换小标i处的元素与flag得到：
“29，34，54”
54左侧的元素比54小，以54左侧的元素构成一个数组得到：
“29，34”
同样flag为第一个元素，下标i为29的下标，下标j为右侧最后一个元素34的下标，开始比较右侧，34>29满足条件，j–,下标j处的元素为29，此时下标i和下标j处的元素为同一个元素，交换flag与下标i处的元素，排序后
“29，34”
此时55左侧的元素顺序为：
“29，34，54”
55右侧只有一个元素67，整个数组的排序已经排完，完整的顺序为：
“4，6，8，12，23，29，34，54，55，67”
整个实现的比较就是上面所说。

实现

#include <QCoreApplication>
#include <stdio.h>

#if 0
void my_print(char text[])
{
    printf(">>>my_print()=%d\n",sizeof(text));
}
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    char test[]="Welcome to China";
    my_print(test);
    printf(">>>main()=%d",sizeof(test));
    return 0;
}
#endif

#if 0
#include <QVector>
#include <QString>
#include <QDebug>
using namespace std;

struct Grade
{
    string name;
    int grade;
};

int main()
{
    Grade subject[3] = {
        { "English", 80 },
        { "Biology", 70 },
        { "History", 90 }
    };

    int sum = accumulate(subject, subject + 3, 0, [](int a, Grade b){return a + b.grade; });
    string strObject = accumulate(subject,subject+3,string(" "),[](string str1,Grade str2){return str1+str2.name;});//accumulate如果是字符串求和，第三个参数必须是string(" ")
    qDebug() << sum<<"strObject="<<strObject.data()/*.c_str()*/;//240

    system("pause");
    return 0;
}
#endif

#include <iostream>
using namespace std;


void outputArr(int *arr,int count){
    for (int i = 0; i < count; ++i) {
        cout<<arr[i]<<" ";
    }
}

//快速排序
void quickSort(int *arr,int left,int right){//left-下标起始值，小标结束值
    if (left >= right) {
        return ;
    }
    int flag = arr[left];
    int i = left;
    int j = right;
    int temp;

    while (i < j) {
        while (i < j && arr[j] >= flag) {//不能排除相等的情况，否则不适用于含有重复元素
            --j;
        }
        while (i < j && arr[i] <= flag) {
            ++i;
        }

        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    if (i == j) {//一轮比较结束后，i和j相等
        temp = arr[i];
        arr[i] =  arr[left];
        arr[left] = temp;
         if(i > left)
        {
            quickSort(arr,left,i-1);
        }
        if(i < right)
        {
            quickSort(arr,i+1,right);
        }
    } 
}

int main()
{
    int nums[] = {23,1,34,4,6,78,33,9,5};
    quickSort(nums,0,6);//传入下标的范围
    outputArr(nums,9);

    cout<<endl;
    cout<<"==========================="<<endl;

    int nums1[] = {7,1,34,4,6,8,33,9,43,6};
    quickSort(nums1,0,9);
    outputArr(nums1,10);
    cout<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

以上便是实现。