排序

算法稳定性

内部排序：在排序期间元素全部存放在内存中的排序

外部排序：在排序期间元素无法全部同时存放在内存中

大多数内部排序都更适用于顺序存储的线性表。

插入排序

直接插入排序

时间复杂度

具有稳定性。

折半插入排序

仅适用于顺序存储的线性表

void insertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1;
        high=-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]>A[0]) high=mid-1;
            else low=mid+1;
            
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];
        
        A[high+1]=A[0];
                   
    }
}

有稳定性，时间复杂度和直接插入排序一样。

希尔排序

取增量，然后不断缩小增量，直到增量为1

void shellsort(int a[],int n){
    int dk,i,j;
    for(dk=n/2;dk>=1;dk=dk/2){
        for(int i=dk+1;i<=n;i++){
            if(A[i]<A[i-dk]){
                A[0]=A[i];
                for(j=i-dk;j>0&& A[0]<A[j];j-=dk){
                    A[j+dk]=A[j];
                   
                }
                A[j+dk]=A[0];
            }
        }
  
}

空间复杂度为

时间复杂度为

不稳定

交换排序

冒泡排序

void bubblesort(int a[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
            if(flag==false)
                return;
        }
    }
}

时间复杂度为

有稳定性

快速排序

void quick_sort(int q[],int l,int r){

    if(l>=r) return ;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) std::swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

//int main(){
//    int a[]={4,3,2,1};
//   quick_sort(a,0,3);
//    for(int i=0;i<=3;i++){
//        cout<<a[i]<<" ";
//    }
//    return 0;
//}

快速排序是所有内部排序算法中平均性能最优的算法。

不具有稳定性

时间复杂度为

递归次数与每次划分后得到的分区处理顺序无关，与初始数据排列顺序有关

对n个元素进行第一趟快速排序之后，会确定一个基准元素，根据这个基准元素的位置有两个情况：

在数组的首端或者尾端，这样子第二次排序之后有两个位置确定。
不在数组首端或者尾端，这样两个子序列会至少有三个位置确定

选择排序

简单选择排序

每次都选最小的那个放到当前序列最前面的地方。

不稳定，时间复杂度

for(int i=0;i<n-1;i++){
    int min=i;
    for(int j=i+1;j<n;j++){
        if(A[j]<A[min]) min=j;
    }
    if(min!=i) swap(A[min],A[i]);
}

堆排序

void maxHeapify(vector<int>&a,int i,int heapSize){
    int l=2*i+1;
    int r=2*i+2;
    int largest=i;
    if(l<heapSize && a[l]>a[largest]){
        l=largest;
    }
    if(r<heapSize && a[r]>a[largest]){
        r=largest;
    }
    if(largest!=i){
        swap(a[largest],a[i]);
        maxHeapify(a,largest,heapSize);
    }
}
// 建堆
void buildMaxHeap(vector<int>&a,int heapsize){
    for(int i=heapsize/2;i>=0;i--){
        maxHeapify(a,i,heapsize);
    }
}
int findKthLargest(vector<int>& nums, int k) {
        int heapSize=nums.size();
        buildMaxHeap(nums,heapSize);
        for(int i=nums.size()-1;i>=nums.size()-k+1;i--){
            swap(nums[0],nums[i]);
            --heapSize;
            maxHeapify(nums,0,heapSize);
        }
        return nums[0];
}

时间复杂度为

不稳定

若从一亿个数中选出前100个最大的数：

首先选择前100个数建立小顶堆

逐渐读入数据，如果小于堆顶就删除，如果大于就替换掉堆顶，然后重新调整堆。

归并排序，基数排序和计数排序

归并排序

void merge(int a[],int b[],int low,int mid,int high){
    // b是辅助数组
    int i,j,k;
    for(k=low;k<=high;k++){
        b[k]=a[k];
    }
    for(i=low,j=mid+1,k=i;i<=mid && j<=high; k++){
        if(B[i]<=B[j]) A[k]==b[i++];
        else A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high) A[k++]=B[j++];
}

void mergeSort(int a,int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

时间复杂度为

有稳定性

基数排序

d个关键字，以r为基数。

举个例子，每个关键字都是1000以下的正整数，基数r=10，先按照最低位子关键字（个位）来排序，然后是十位，最后是百位。

空间复杂度

计数排序

对于每个待排序的元素x，统计小于x的元素的位置。

void CountSort(int a[],int b[],int n,int k){
    int i,C[k];
    for(i=0;i<k=i++) C[i]=0;
    for(i=0;i<n;i++) C[A[i]]++;
    for(i=1;i<n;i++) C[i]=C[i]+C[i-1];
    for(int i=n-1;i>=0;i--){
        B[--C[A[i]]]=A[i];
    }
}
// B存放输出的排序序列
// C存放计数值