C/C++实现经典排序算法

绝地灬酷狼 2021-11-16 10:52 286阅读 0赞

## C/C++实现经典排序算法（重要性：快速排序 > 归并排序 > 选择排序） ##

**1、快速排序：采用分治思想，时间O(nlogn)  空间O(logn) 不稳定 交换位置的次数不恒定(次数受原序列是否有序的限制，越有序越快)**

void quick_sort(int arr[],int left,int right){
        if(left > right)
            return;
        int i,j,tmp;
        i=left;
        j=right;
        tmp=arr[left];  //我们最开始选left位置的数作为基数，由tmp暂存
        while(i!=j){
            while(arr[j]>=tmp && i<j)
                j--;
            while(arr[i]<=tmp && i<j)
                i++;
            if(i<j){
                arr[i]=arr[i]^arr[j];
                arr[j]=arr[i]^arr[j];
                arr[i]=arr[i]^arr[j];
            }
        }
        arr[left]=arr[i]; //i已经到了指定位置了，即i位置左边的都比它小，右边的都比它大
        arr[i]=tmp;  //将基数放到最后的准确位置
        quick_sort(arr,left,i-1);
        quick_sort(arr,i+1,right);
    }

**2、归并排序：采用分治策略，先分治，再合并，稳定，时间复杂度O(nlog2n) ，空间复杂度O(n)**

void merge(int arr[],int low,int mid ,int high){
        int i=low,j=mid+1,k=0;
        int tmp[high-low+1];
        while(i<=mid && j<=high){
            if(arr[i] < arr[j])
                tmp[k++]=arr[i++];
            else
                tmp[k++]=arr[j++];
        }
        while(i<=mid)
            tmp[k++]=arr[i++];
        while(j<=high)
            tmp[k++]=arr[j++];
        for(int x=0;x<high-low+1;x++)
            arr[low+x]=tmp[x];
    }
    void merge_sort(int arr[],int low,int high){
        if(low < high){
            int mid = low +(high - low)/2;
            merge_sort(arr,low,mid); //分治，划分数组
            merge_sort(arr,mid+1,high); //分治疗，划分数组
            merge(arr,low,mid ,high);//做合并
        }
        return;
    }

**3、选择排序：不稳定 时间复杂度O(n^2) ，空间复杂度O(1)**

int select_sort(int arr[],int len){   //一次循环就将最值放到最边上
        int i,j;
        for(i=len-1;i>1;i--){
            int MAX=i;
            for(j=0;j<i;j++){
                if(arr[j]>arr[MAX])
                    MAX=j;
            }
            if(MAX!=i){  //不能自己跟自己交换位置
                arr[i]=arr[i]^arr[MAX];
                arr[MAX]=arr[i]^arr[MAX];
                arr[i]=arr[i]^arr[MAX];
            }
        }
    }

**4、插入排序：稳定 时间复杂度O(n^2) 空间复杂度O(1)**

void insert_sort(int arr[],int size){
        int i,j,key;
        for(i=1;i<size;i++){
            key=arr[i];
            for(j=i-1;j>=0;j--){
                if(key<arr[j])
                    arr[j+1]=arr[j];
                else
                    break;
            }
            arr[j+1]=key;
        }
    }

**5、希尔排序：时间O(nlogn)，空间O(1)，不稳定**

void shell_sort(int a[],int len){
        int j,tmp;
        for(int h=len/2;h>0;h/=2){
            for(int i=h;i<len;i++){
                tmp=a[i];
                for(j=i-h;j>=0;j-=h)
                    if(a[j]>tmp)
                        a[j+h]=a[j];
                    else
                        break;
                a[j+h]=tmp;
            }
        }
    }

**6、冒泡排序：稳定 时间复杂度O(n^2) 空间复杂度O(1)**

void bubble_sort(int arr[],int size){
        for(int i=0;i<size;i++)
            for(int j=0;j<size-i;j++)
                if(arr[j]>arr[j+1]){
                    arr[j]=arr[j]^arr[j+1];
                    arr[j+1]=arr[j]^arr[j+1];
                    arr[j]=arr[j]^arr[j+1];
                }
    }

**7、堆排序：****不稳定 时间复杂度O(nlog2n) 空间复杂度O(1)**

/*********堆排序 不稳定 时间复杂度O(nlog2n) 空间复杂度O(1)***********/
    void swap(int *a,int *b){  //指针交换成功
    	int tmp;
    	tmp=*a;
    	*a=*b;
    	*b=tmp;
    }
    void adjust(int a[],int len,int root){
    	int left=2*root+1,right=2*root+2;
    	int max=root;
    	if(left<len && a[left]>a[max])
    		max=left;
    	if(right<len && a[right]>a[max])
    		max=right;
    	if(max!=root){
    		swap(a+root,a+max);
    		adjust(a,len,max);
    	}
    }
    void creat_heap(int a[],int len){
    	for(int i=(len/2)-1;i>=0;i--)
    		adjust(a,len,i);
    }
    void heap_sort(int a[],int len){
    	creat_heap(a,len);
    	for(int i=0;i<len;i++){
    		swap(&a[0],&a[len-1-i]);
    		adjust(a,len-1-i,0);
    	}
    }
    /******************************************************************/

**最后附上算法对比表：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ZW5nd2VpMTMxMw_size_16_color_FFFFFF_t_70][]

纠错：快排采用递归调用，空间复杂度是logN.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h6ZW5nd2VpMTMxMw_size_16_color_FFFFFF_t_70]: /images/20211116/82a572cbabb54a83b09616dd22459ad5.png