快速排序算法(Quick_Sort)

快速排序(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;
}

三.代码实现(c++)

#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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!