快速排序(Quick_Sort)

一、介绍:

快速排序（Quick_sort）是对冒泡排序算法的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序

中文名: 快速排序算法

外文名: quick sort

别 名: 快速排序

时间复杂度：O(nlogn)

稳定性：稳定

提出者: C. A. R. Hoare

提出时间: 1960年

二、逻辑

1.将数分为两个部分，假设数中用一值为v，第一部分 < v , 第二部分 > v ;然后将这两部分进行递归调用，然后每一部分又分成了子两部分，再将每一个子部分进行递归调用，依次递归下去，直到每一个元素为止。

2.例如：(文字有点多，请耐心看完，跟着逻辑走)

数组arr{5, 4, 7, 2, 1, 8},首先我们取一个值作为（二.1）中v；我们也可以使用arr中的任何一个元素(如果取任意数j就需要使用生成随机数的methods），这里我们就用第一个元素，即v = 5；

(1) 将v放在一边从第二个数开始比较此时：arr[1] = 4;

Arr[1] < v,将arr[1]放置数组左边(此时已是左边)，然后比较arr[2] = 7;

(2）arr[2] > v, 所以将arr[2]放置右边(此时遍历刚开始，后面的元素还未遍历，此时arr[2]相对于遍历的元素已经是右边，arr[2])仍为原来位置），再进行下一个元素的比较 arr[3] = 2;

(3) arr[3] < v,所以需要将arr[3]放置素组的左边从而得到数组：

arr{5, 4, 2, 7, 1, 8}

再比较下一个元素 arr[4] = 1;

(4) arr[4] < v,所以需要将arr[4]放置素组的左边从而得到数组：

arr{5, 4, 2,1, 7, 8}

再比较下一个元素 arr[5] = 8

(5) arr > v 所以需要将arr[5]放置素组的右边从而得到数组：

arr{5, 4, 2,1, 7, 8}

***此时第一步已经完成，接下来将arr{5, 4, 2,1, 7, 8}中，

{arr{ 4, 2,1, 7, 8}进行递归，将 > v 和 < v的元素分为两部分，如下：

Arr1{, 4, 2,1}和arr2{ 7, 8}将两数组再进行上述2.(1）~ 2.(5)操作，一直直到递归到每一个元素本身为止

最后将每一个v将插入两”< v”和”> v”之间，就可的到排序完成的数组

arr{1, 2, 4, 5, 7, 8}

2.(1）~ 2.(5)操作为构造函数为partition

#include <iostream>
using namespace std;

template<typename T> //使用模板函数
int partition(T arr[], int l, int r){
    int v = arr[l];
    int j = l;
    for(int i=j+1; i<=r; i++){
        if(arr[i] < v){
           swap(arr[j+1], arr[i]);
           j++;
        }

}
    swap(arr[l], arr[j]);
    return j;
}

三.代码实现

#include <iostream>
using namespace std;

template<typename T>
int partition(T arr[], int l, int r){
    //也可用生成随机数的方法来取数组中任意数
    int v = arr[l];
    int j = l;
    for(int i=j+1; i<=r; i++){
        if(arr[i] < v){
          //swap函数来自c++库
            j++
            swap(arr[j], arr[i]);
        }

    }
    swap(arr[l], arr[j]);
    return j;

}

template<typename T>
void __quicksort(T arr[], int l, int r){
  //递归限制条件
    if(l>=r)
        return;

    int p = partition(arr, l , r);
  //递归调用
    __quicksort(arr, l, p-1);
    __quicksort(arr, p+1, r);

}
//定义函数QuickSort
template<typename T> //使用模板函数
void QuickSort(T arr[], int n){

    __quicksort(arr ,0, n-1);
}

下面做一个简单测试：

int main() {
    int n;
  //请输入元素个数
    cin>>n;
    int a[n];
  //这里我使用指针
    int *p;
    p = a;
    for(int i=0; i<n; i++) {
        cin >> *(p+i);
    }
    QuickSort(p, n);
    for(int i=0; i<n; i++){
        cout<<*(p+i)<<endl;
    }
    return 0;
}

如果不使用指针：

int main() {
    int n;

    cin>>n;
    int a[n];
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    QuickSort(a, n);
    for(int i=0; i<n; i++){
        cout<<a[i]<<endl;
    }
    return 0;
}

请输入元素个数：5
5
4
3
2
1

输出结果如下：

1
2
3
4
5

Process finished with exit code 0

本作品采用《CC 协议》，转载必须注明作者和本文链接