sort快排的实现

快速排序的基本实现

快速排序算法是一种基于交换的高效的排序算法，它采用了分治法的思想：
1、从数列中取出一个数作为基准数。
2、将数组进行划分，将比基数大的元素都移至基准数的右边，将小于等于基准数的元素都移至基准数的左边。
3、再对左右的子区间重复第二步的划分操作，直至每一个子区间只有一个元素。

快速排序实现一：

#include <iostream>
using namespace std;
void quick_sort(int arr[], int left,int right);
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    quick_sort(a,0,n-1);
    for(int i=0; i<n; i++){
        cout<<a[i]<<"\t";
    }

    return 0;
}
//快排
int partition(int arr[], int left,int right){
    //找基准数 划分（分治）
    int i=left + 1;
    int j=right;
    int temp = arr[left];
    while(i<=j){
        while(arr[i]<temp){
            i++;
        }
        while(arr[j]>temp){
            j--;
        }
        if(i<j){
            swap(arr[i],arr[j]);
            i++;
            j--;
        }else{
            i++;
        }
    }
    swap(arr[j],arr[left]); 
    return j;
}

void quick_sort(int arr[], int left, int right){
    if(left>right){
        return;
    }
    int j = partition(arr,left,right);
    quick_sort(arr,left,j-1);
    quick_sort(arr,j+1,right);  
}

快速排序 实现方法二：

#include <iostream>
using namespace std;
//声明 Quick_sort快排方法 
void Quick_sort(int arr[], int start, int last);
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    Quick_sort(a,0,n-1);
    for(int i=0; i<n; i++){
        cout<<a[i]<<"\t";
    }

    return 0;
}

void Quick_sort(int arr[], int start, int last){
    int i = start;
    int j = last;
    int temp = arr[i];
    if(i<j){
        while(i<j){
            while(i<j && arr[j]>=temp){
                j--;
            }
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            while(i<j && temp>arr[i]){
                i++;
            }
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        //把基准数放到i位置
        arr[i] = temp;
        //递归方法
        Quick_sort(arr,start,i-1);
        Quick_sort(arr,i+1,last); 
    }   
}

快排的时间复杂度

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

快速排序的稳定性

快速排序是不稳定的算法。
算法稳定性：假设在数列中存在啊a[i]=a[j],若在排序之前，啊a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面，则说这个排序算法是稳定的。