一、八大排序（sort）

一、时间复杂度

（一）定义：常数操作

与数据量无关，是一个固定的东西。
一个操作如果和样本数量没有关系，每次都是固定时间内完成的操作，就叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的一个指标。常用o(读作big o)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

二、空间复杂度

（一）定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势。

三、排序

（一）选择排序

1.定义

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.代码

void process(vector<int> &arr) {
    if (arr == nullptr || arr.size() < 2) {
        return ;
    }
    for (int i = 0 ; i < arr.size() - 1; i++) { // 当前位置
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr,i,minIndex);
    }
}
void swap(vector<int> &arr,int j,int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.特性

• 容易理解,但是效率太低,实际当中不太使用

• 时间复杂度O(n^2),空间复杂度O(1);

• 不稳定

（二）冒泡排序

1.定义

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

2.代码

void bubbleSort(vector<int> &arr) {
    if (arr == nullptr || arr.size() < 2) {
        return ;
    }
    int n = arr.size();
    for (int i = 0; i < n; i++) { // //控制交换次数
        for (int j = 0; j < n - i - 1; j ++) { // //向后冒泡 ,控制边界
            if(arr[j] > arr[j+1])//如果前一个值大于后一个值,交换
			{
				swap(arr[j],arr[j+1]);
			}		
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.特性

• 容易理解
• 时间复杂度O(n^2),空间复杂度O(1)
• 稳定

（三）插入排序

1.定义

插入排序的步骤如下：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。

例：对于数组 [3,2,5,4,2,3,3] 进行插入排序的详细过程：
1、0~0位置上做到有序 ——>就一个数 做到了
2、0~1位置上做到有序 ——>2比3小 2 3互换位置——> [2,3,5,4,2,3,3]
3、0~2位置上做到有序 ——>5比3大 位置不动——> [2,3,5,4,2,3,3]
4、0~3位置上做到有序 ——>4比5小 4 5互换位置——> [2,3,4,5,2,3,3]——>4比3大 位置不动
5、0~4位置上做到有序 ——>2比5小 2 5互换位置——> [2,3,4,2,5,3,3]
  ——>2比4小 2 4互换位置——> [2,3,2,4,5,3,3]——>2比3小 2 3互换位置——> [2,2,3,4,5,3,3]
  2比2相等 位置不动
6、0~5位置上做到有序 ——>3比5小 3 5互换位置——> [2,2,3,4,3,5,3]
  ——>3比4小 3 4互换位置——> [2,2,3,3,4,5,3]——>3比3相等 位置不动
7、0~6位置上做到有序 ——>3比5小 3 5互换位置——> [2,2,3,3,4,3,5]
  ——>3比4小 3 4互换位置——> [2,2,3,3,3,4,5]——>3比3相等 位置不动

2.代码

void insertSort(vector<int> &arr) {
    if (arr == nullptr || arr.size() < 2) {
        return ;
    }
    
    for (int i = 1; i < arr.size(); i++) { // 0 - 0 有序的
    
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1] ; j--) { // 想有序
            swap(arr,j, j + 1);
        }
        
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.特性

• 元素集合越接近有序，直接插入排序算法的时间效率越高
• 时间复杂度:O(n^2)(情况最差时,即逆序转有序,最好为O(n));
• 空间复杂度:O(1);
• 稳定

（四）归并排序

1.定义

对于一个数组从中点的位置分开，先让左侧部分排好序，再让右边部分排好序，然后整体整合。

将图中左侧部分和右侧部分分别排好序，然后使用两个指针分别从两部分的最左侧开始，在内存中单独开辟一个空间 ，这时我们比较两个指针指向的数的大小，左侧小于等于右侧的时候，将左侧部分指针指向的值拷贝到辅助空间中，然后左侧指针右移一位。如果右侧部分指针指向的值小于左侧的，则将右侧部分指针指向的值拷贝到辅助空间中，然后右侧指针右移一位。依次循环，如果哪侧越界了，将剩下的部分直接拷贝到辅助空间中。将辅助空间拷贝到原数组。

2.代码

#include
using namespace std;
vector<int> ans;
void merge(int l,int mid,int r) {
	int i = l,j = mid + 1,k = 0;
	vector<int> temp(r - l + 1);
	while (i <= mid && j <= r) {
		if(ans[i] <= ans[j]) {
			temp[k++] = nums[i ++];
		}
		else {
			temp[k++] = nums[k ++];
		}
	}
	while (j <= r) {
		temp[k ++] = nums[j ++];
	}
	while (i <= r) {
		temp[k ++] = nums[i ++];
	}
	for (int i = l,k = 0; i <= r; i++,k ++) {
		nums[i] = temp[k];
	}
}
void mergesort(vector<int> &nums,int l,int r) {
	if (l >= r) return;
	int mid = l + (r - l) / 2;
	mergesort(nums,l,mid);
	mergesort(nums,mid + 1,r);
	merge(l,mid,r);
	
}
int main() {
	int n;
	cin >> n;
	ans.resize(n);
	for (int i = 0 ; i < n; i++) {
		cin >> nums[i];
	}
	sort(ans,0,n - 1);
	return 0;
}
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
32
33
34
35
36
37
38
39
40
41
42

3.特性

• 整体就是简单的递归，左边排好序、右边排好序、让整体有序
• 让其整体有序的过程里用了排外序的方法
• 利用master公式来求解时间复杂度
• 归并排序的实质

（五）快速排序

1.定义

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1、首先设定一个分界值，通过该分界值将数组分成左右两部分。

2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

概括来说为 挖坑填数 + 分治法。

2.代码

#include
#include
using namespace std;
vector<int> nums;
void quicksort(vector<int>& nums,int l,int r) {
    if (l >= r) { return ;}

    int i = l - 1,j = r + 1,mid = nums[(l + r) >> 1];
    while (i < j) {
        do i ++; while (nums[i] < mid);
        do j --; while (nums[j] > mid);
        if (i < j) swap(nums[i],nums[j]);
    }
    quicksort(nums,l,j);
    quicksort(nums,j + 1,r);
}
int main() {
    int n;
    cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i ++) {
        cin >> nums[i];
    }
    quicksort(nums,0,n - 1);
    for (int i = 0; i < n; i++) {
        cout << nums[i] << endl;
    }
    return 0;
}
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

（六）堆排序

1.定义

一、算法思想
堆排序是利用堆性质进行的一种选择排序
概念：
堆：堆是一棵顺序存储的完全二叉树
每个节点的值都不大于其左右孩子节点的值的堆叫做小根堆（下左图）
每个节点的值都不小于其左右孩子节点的值的堆叫做大根堆（下右图）

设当前元素在数组中以R[i]表示，那么，

(1) 它的左孩子结点是：R[2*i+1];

(2) 它的右孩子结点是：R[2*i+2];

(3) 它的父结点是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

2.代码

（七）基数排序

（八）计数排序