七、排序

1.时间复杂度

​ 平均情况下，快排，希尔排序（复杂度了解即可）、归并排序和堆排序的复杂度为O(nlog²n)，其他都是O(n²)。一个特殊的是计数排序，其复杂度为O(n*k)

​ 最坏情况下，快速排序的为O(n²)，其他都和平均情况下相同

2.空间复杂度

​ 快排O(nlog²n)，归并O(n)，基数O(n+k)，其他都是O(1)

快排、希尔、简单选择、堆排序是不稳定的，其余均为稳定的。

插入排序

时间复杂度：最好O(n) 最坏O(n²) 平均O(n²)

空间复杂度：O(1)

稳定

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(int arr[],int n){
	for(int i = 1; i < n;i++){
		int t = arr[i];//t等于当前元素
		int j = i;//j从当前元素开始往前看
		while(j&&t < arr[j-1]){//j>0且前一个元素也是大于t的时候
			arr[j] = arr[j-1];//将前一个元素往后移动一位
			j--;//j往前移动一位
		}
		arr[j] = t;//将t放到对应的元素上
	}
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void binary_sort(){
    for(int i=1;i<n;i++){
//如果前一个元素比当前元素要小或相等我们就不需要改变位置直接跳过，否则必然存在比当前元素大的元素
        if(a[i-1]<a[i])continue;
        int t=a[i],l=0,r=i-1;
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>t)//如果中间元素是大于当前元素
                r=mid;//二分的点为当前元素的左边
            else l=mid+1;//二分的点为当前元素的右边
        }
        for(int j=i-1;j>=r;j--){//将i-1开始到r这一部分元素从后往前移动一位
            a[j+1]=a[j];
        }
        a[r]=t;//将当前元素存放到r的位置上
    }
}

希尔排序

时间复杂度：最好O(nlog²n) 最坏O(nlog²n) 平均O(nlogn)

空间复杂度：O(1)

不稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//时间复杂的O(n^2)
//空间复杂度O(1)
//稳定性：不稳定排序
void ShellSort(int num[],int len){
	for(int d = len / 2;d > 0;d /= 2){//逐渐缩小间隔，最终为1
        for(int start = 0;start < d;start++){//枚举一下每个序列的起点
            for(int i = start + d;i < len ; i++){//在这里做插入排序
                int t = num[i];
                int j = i;//从下标为0开始存储
                while(j > start && num[j - d] > t){
                    num[j] = num[j - d];
                    j -= d;		//依次移动step个位置
                }
                num[j] = t;
            }
        }
	}
}

冒泡排序

时间复杂度：最好O(n) 最坏O(n²) 平均O(n²)

空间复杂度 O(1)

稳定

1
2
3
4
5
6
7
8
9
10
void Bubble_Sort(int arr[],int len){
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

快速排序

时间复杂度：最好O(nlogn) 最坏为O(n²) 平均O(nlogn)

空间复杂度：O(logn)

不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void Quick_Sort(int arr[],int l,int r){
    int i = l,j = r;
    if(l < r){
        int temp = arr[l];
        while(i < j){
            //从右向左找第一个小于temp的数
            while(i < j && arr[j] >= temp)
                j--;
            if(i < j){
                arr[i] = arr[j];
                i++;
            }
            //从左向右找第一个大于等于temp的数
            while(i < j && arr[i] < temp)
                i++;
            if(i < j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = temp;
    }
    //递归调用
    Quick_Sort(arr,l, i - 1);
    Quick_Sort(arr,i + 1,r);
}

选择排序

时间复杂度：最好O(n) 最坏O(n²) 平均O(n²)

空间复杂度：O(1)

不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Selection_Sort(int arr[],int len){
    int i,j,temp;
    for (i = 0 ; i < len - 1 ; i++) {
        int k = i;// 记录最小值，第一个元素默认最小
        for (j = i + 1; j < len; j++)// 访问未排序的元素
            if (arr[j] < arr[k])// 找到目前最小值
                k = j;    // 记录最小值  
        if(k != i){
            temp=arr[min]; // 交换两个变量
            arr[min]=arr[i];
            arr[i]=temp;
        }
    }
}

堆排序(看成完全二叉树，根结点要么最大要么最小)

时间复杂度：最好O(nlogn) 最坏为O(nlogn) 平均O(nlogn)

空间复杂度：O(1)

不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//先“筛选” （堆顶到叶子的调整过程）
//在 low 到 high 范围内对 low 进行调整
void sift(int arr[],int low,int high){
	int i,j;
	i=low,j=2*i;
	int temp=arr[low];//以 low 为根向下交换
	while(j<=high){
		if(j<high&&arr[j]<arr[j+1])//大顶堆 与较大的孩子进行比较
			j++;
		if(temp<arr[j]){
			arr[i]=arr[j];
			i=j;
            j=2*i;
		}
		else
			break;
	}
	arr[i]=temp;
}
//排序
void Heap_Sort(int n,int arr[]){
	int temp;
	for(int i=n/2;i>=1;i--)
		sift(arr,i,n);//建堆
	for(int i=n;i>=2;i--){//排序
		temp=arr[1];//每次和最大值交换
		arr[1]=arr[i];
		arr[i]=temp;
		sift(arr,1,i-1);//只需要调整一次就好
	}
}

二路归并排序

时间复杂度：最好O(nlogn) 最坏为O(nlogn) 平均O(nlogn)

空间复杂度：O(n)

稳定

思想：先两两归并，然后两两归并，最后两两归并

对于一个左边一半和右边一半分别有序的数组，合并成一个新的整体有序的数组，需要注意的是，这里需要一个和原数组一样大的辅助空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void MergrSort(int arr[],int n,int low,int high){
    if(low < high){
        int mid = (low + high) / 2;
        MergrSort(arr, low, mid);	//递归排序左边，下标从low到mid是有序
        MergrSort(arr, mid+1, high);//递归排序右边，下标从mid到high是有序的
        int temp[Maxn];//新开一个数组来辅助排序，将两个有序数组合并成一个有序数组
        int i = low,j = mid + 1,k = 0;//i从左区间的第一个元素开始走，j从右区间第一个元素开始走，k是临时数组下标
        while(i <= mid && j <= high){//如果左右区间都没有走完
            if(arr[i] <= arr[j]){//如果左边的值小于右边的值
                temp[k++] = arr[i++];//将左边的值赋值给临时数组
            }
            else{
                temp[k++] = arr[j++];//将右边的值赋值给临时数组
            }
        }
        while(i <= mid){//如果左边没有走完，继续赋值。
            temp[k++] = arr[i++];
        }
        while(j <= high){//如果右边没有走完，继续赋值。
            temp[k++] = arr[j++];
        }
        for(i = low,j = 0;j < k;i++,j++)//将临时数组的元素复制给原数组
            arr[i] = temp[j];
        }
}

基数排序

时间复杂度：最好O(n * k) 最坏为O(n * k) 平均O(n * k)

空间复杂度：O(n + k)

稳定