【数据结构】快速排序

对于一个int数组，请编写一个归并排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：
[1,2,3,5,3],6
[1,5]

思路：
1， 选取第一个为哨兵，不要随机选取
2， 在交换的时候一定要注意偏移量，left一定要加上，不然通不过测试。
3， 统计完小于哨兵的counter后，交换一次key和A[counter]即可。

#include<iostream>
#include<string>
using namespace std;


class QuickSort {
public:

    void print(int * A,int n){
        for (int i = 0; i < n; i++)
            printf("%d ",A[i]);
        printf("n");
    }

    void swap(int * A,int * B){
        int temp = *A;
        *A = *B;
        *B = temp;
    }

    void proccess(int * A,int left,int right){
        if (left >= right)
            return;

        int shao = A[left];

        int counter = 0;    //哨兵的index
        swap(A + left,A + right);
        for (int i = left; i < right; i++){
            if (A[i] <= shao){
                swap(A + i,A + left + counter);
                counter++;
            }
        }
        swap(A + left + counter,A + right);
        proccess(A,left,left + counter -1);
        proccess(A,left + counter + 1,right);
    }

    int* quickSort(int* A,int n) {
        // write code here 

        proccess(A,0,n - 1);

        return A;
    }
};


int main()
{
    QuickSort s;

    int A[] = { 54,35,48,36,27,12,44,8,14,26,17,28 };
    int n = 13;
    s.quickSort(A,n);
    s.print(A,n);

}

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!