本文共 7501 字，大约阅读时间需要 25 分钟。

1、冒泡排序

1.1 算法思路

• 比较相邻的元素，如果第一个比第二个大，那么就交换这两个元素。
• 从第一对到最后一对的比较，那么最后的元素就是最大的，重复上述的步骤。

1.2 代码实现

// 冒泡排序void BubbleSort(vector<int> & nums){   	int len = nums.size();	for (int i = 0; i < len - 1; ++i)	{   		for (int j = 0; j < len - 1 - i; ++j)		{   			if (nums[j] > nums[j + 1])			{   				swap(nums[j], nums[j + 1]);			}		}	}}

1.3 冒泡排序优化

1.4 复杂度

• 时间复杂度
• 最坏：O(n²)
• 最好：O(n)
• 空间复杂度
• O(1)

1.5 优缺点

• 优点
• 简单，稳定
• 缺点
• 时间复杂度过大

2、选择排序

2.1 算法思路

• 首先在序列中找到最大(小)的元素，放到排序序列的起始位置。
• 在从剩余未排序的元素中寻找最大(小)的元素放到已排序序列的末尾

2.2 代码实现

// 选择排序void SelectSort(vector<int>& nums){   	int len = nums.size();	for (int i = 0; i < len - 1; i++)	{   		int maxPos = 0; // 找到的最大值的位置		for (int j = 0; j < len - i; j++)		{   			if (nums[j] > nums[maxPos])				maxPos = j;		}		if (maxPos != len - 1 - i)			swap(nums[len - i - 1], nums[maxPos]);		}}

2.3 算法分析

• 无论什么数据进去时间复杂度都是O(n²)，所以用它的时候数据规模越小越好。
• 唯一的好处是不占用额外的空间

时间复杂度：

• 最坏 / 优：O(n²)

空间复杂度：

• O(1)

2.4 选择排序优化

3、插入排序

3.1 算法思路

• 从第一个元素开始，第一个元素被认为是排序好的
• 取出下一个元素，从已经排好序的序列中从前开始比较
• 如果大于该元素大于新元素，将该元素移动到下一个位置，否则重复这个过程，直到找到小于等于新元素的位置
• 然后将新元素插入到该位置

3.2 代码实现

// 插入排序void InsertSort(vector<int>& nums){   	int len = nums.size();	for (int i = 1; i < len; ++i)	{   		int tmp = nums[i];		int end = i - 1;		while (end >= 0 && tmp < nums[end])		{   			nums[end + 1] = nums[end];			end--;		}		nums[end + 1] = tmp;	}}

3.3 算法分析

插入排序在实现上，空间复杂度O(1)，在向前扫描的过程中，需要反复把排序元素向后搬移。

3.4 链接

4、希尔排序

4.1 算法思路

• 将整个待排序的序列分割成若干个子序列分别进行直接插入排序
• 每趟排序，将待排序分割成若干长度为m的子序列，分别对各子表进行直接插入排序。

4.2 代码实现

// 希尔排序void ShellSort(vector<int>& nums){   	int gap = 3;	int len = nums.size();	while (gap >= 1)	{   		for (int i = gap; i < len; ++i)		{   			int tmp = nums[i];			int end = i - gap;			while (end >= 0 && tmp < nums[end])			{   				nums[end + gap] = nums[end];				end -= gap;			}			nums[end + gap] = tmp;		}		gap--;	}}

4.3 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设置间隔序列，也可以动态的定义间隔序列。

4.4 链接

5、归并排序

5.1 算法思路

• 将已有序的子序列合并，得到完全有序的序列。
• 先将每个子序列有序，再使子序列段间有序
• 若将两个有序表合并成一个有序表，那么称之为二路归并

5.2 代码实现

// 归并排序void MergeData(int *nums, int left, int mid, int right, int* temp){   	// 先将数组分为两个部分，一个从头开始，一个从中间开始	int begin1 = left, end1 = mid;	int begin2 = mid, end2 = right;	// index表示temp的下标	int index = left;	// 循环将小的放到temp中	while (begin1 < end1 && begin2 < end2)	{   		if (nums[begin1] > nums[begin2])			temp[index++] = nums[begin2++];		else			temp[index++] = nums[begin1++];	}	// 处理还没有排序的数字	while (begin1 < end1)		temp[index++] = nums[begin1++];	while (begin2 < end2)		temp[index++] = nums[begin2++];}void _MergeSort(int* nums, int left, int right, int* temp){   	int mid = left + ((right - left) >> 1);	// 采用递归的方式	if (right - left > 1)	{   		_MergeSort(nums, left, mid, temp);		_MergeSort(nums, mid, right, temp);		MergeData(nums, left, mid, right, temp);		// 这里一定要加上left，因为你排了左边，还有右边要排，右边的下标也得加上left		memcpy(nums + left, temp + left, (right - left)*sizeof(nums[0]));	}}void MergeSort(int* nums, int size){   	// 开辟一个辅助空间		int* temp = (int*)malloc(sizeof(nums[0] * size));	// 空间检测是否开辟成功	if (NULL == temp)	{   		assert(0);		return;	}	_MergeSort(nums, 0, size, temp);	//free(temp);}

5.3 算法分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好得多，因此时间复杂度始终是O(nlogn)。需要大量的额外的空间。

5.4 链接

6、快速排序

6.1 算法思路

• 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键比另一部分的关键字小，然后对这两部分记录继续进行排序

6.2 代码实现

int Partion1(int* array, int left, int right){   	int begin = left;	int end = right - 1;	//设置基准值，取数组最右侧的元素	int key = array[end];	while (begin < end)	{   		//寻找大于基准值的数		while (begin < end && array[begin] <= key)			begin++;		while (begin < end && array[end] >= key)			end--;		if (begin < end)			Swap(&array[begin], &array[end]);	}	//这里将基准值和begin（end）交换	if (begin != right - 1)		Swap(&array[begin], &array[right - 1]);	return begin;//此时应该返回begin，key只是值（这里是下标操作）}

6.3 快速排序优化

6.4 快速排序特点

优点：

• 速度快，平均性能好，O(nlogn)

缺点：

• 不稳定，初始序列有序或基本有序，O(n²)

空间复杂度：

• 递归：O(nlogn)

7、堆排序

7.1 算法思路

• 利用堆是一个近似完全二叉树的结构
• 将堆顶元素和最后一个元素交换，然后对于违反堆的性质的区域进行调整

7.2 代码实现

// 堆排序void Adjust(vector<int> & nums, int len, int index){   	int left = 2 * index + 1;	int right = 2 * index + 2;	int maxIdx = index;	if (left < len && nums[left] > nums[maxIdx]) maxIdx = left;	if (right < len && nums[right] > nums[maxIdx]) maxIdx = right;	if (maxIdx != index)	{   		swap(nums[maxIdx], nums[index]);		Adjust(nums, len, maxIdx);	}}void HeapSort(vector<int>& nums){   	int len = nums.size();	// 从最后一个非叶子节点开始向上调整	for (int i = len / 2 - 1; i >= 0; --i)	{   		Adjust(nums, len, i);	}	// 调整大堆	for (int i = len - 1; i >= 1; --i)	{   		swap(nums[0], nums[i]);		// 调整违反堆性质的区域		Adjust(nums, i, 0);	}}

7.3 堆排序优缺点

优点：

• 堆排序效率稳定，不像快排在极端情况下是O(n²)，不管有序还是不有序，时间复杂度都是O(nlogn)
• 堆排序，快速排序，归并排序都达到了比较排序算法的峰值
• 高效并且节省空间，空间复杂度O(1)

缺点：

• 堆排序最大的缺点就是堆的维护问题。
• 当数据是频繁的发生变化时，每次都要更新待排序序列，我们做一遍堆的维护，才能保证它的特性。

7.4 堆的实现

8、计数排序

8.1 算法思路

• 将输入的数据转化成键存储在额外开辟的数组空间。
• 找出待排序列的数组中最大和最小的元素
• 统计每个值为i的元素出现的次数，存入数组C的第i项
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

8.2 代码实现

void countSort(int* nums, int size){   	// 1.找到最大的值	int max = nums[0];	for (int i = 0; i < size; ++i)	{   		if (nums[i] > max)			max = nums[i];	}	// 2.确定数组的长度并进行初始化	int* countData = new int[max + 1];	for (int i = 0; i <= max; ++i)	{   		countData[i] = 0;	}	// 3.遍历数组，统计每个数字的次数	for (int i = 0; i < size; ++i)		++countData[nums[i]];	// 4.累计输出数字	int index = 0;	for (int i = 0; i <= max; ++i)	{   		for (int j = 0; j < countData[i]; ++j)		{   			nums[index++] = i;		}	}}

8.3 算法分析

计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何排序算法。当k不是很大且序列比较集中时，计数排序是一个很有效的排序算法。

对于计数排序的空间复杂度，为了不污染原数组，可以开辟新的数组来保存最后排序的结果，所以空间复杂度是O(n+k)，k表示开辟的辅助空间的大小。
 

9、桶排序

9.1 算法思路

• 桶排序是计数排序的升级版。
• 计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。
• 通过映射函数，将待排序数组中的元素映射到各个对应的桶中。
• 对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

9.2 代码实现

#include <iostream>#include <vector>#include <limits.h>#include <algorithm>void BucketSort(std::vector<int>& vec){     int len = vec.size();  int Max = INT_MIN;  int Min = INT_MAX;  // 1.计算出最大最小值  for(int i = 0; i < len; ++i)  {       if(vec[i] > Max){         Max = vec[i];    }    if(vec[i] < Min){         Min = vec[i];    }  }  // 2. 计算出桶的数量  int bucketnum = (Max - Min) / len + 1;  std::vector<std::vector<int>> temp(bucketnum);    // 3. 将元素放入桶内  for(int i = 0; i < len; ++i)  {     	// 计算出该数字在哪个桶中    int num = (vec[i] - Min) / bucketnum;    temp[num].push_back(vec[i]);  }  // 4. 对桶内的元素进行排序  for(int i = 0; i < bucketnum; ++i){       sort(temp[i].begin(), temp[i].end());  }  // 5. 将桶中的元素赋值给原序列  int index = 0;  for(int i = 0; i < bucketnum; ++i)  {       int knum = temp[i].size();    int j = 0;    while(j < knum)    {         vec[index++] = temp[i][j++];    }  }}

9.3 算法分析

桶排序最好情况下使用线形时间O(n)，桶排序的时间复杂度取决于各个桶之间数据进行排序的时间复杂度，因此其他部分的时间复杂度都为O(n)。很显然，桶划分越小，各个桶之间的数据越少，排序所用的时间也就越少。
 

10、基数排序

10.1 算法思路

• 基数排序是按照低位优先，然后收集，在按照高位排序，然后在收集，以此类推，知道最高位。

10.2 代码实现

// 基数排序int maxbit(int data[], int n){   	int d = 1; //保存最大的位数	int p = 10;	for (int i = 0; i < n; ++i)	{   		while (data[i] >= p)		{   			p *= 10;			++d;		}	}	return d;}void radixsort(int data[], int n) //基数排序{   	int d = maxbit(data, n);	int tmp[n];	int count[10]; //计数器	int i, j, k;	int radix = 1;	for (i = 1; i <= d; i++) //进行d次排序	{   		for (j = 0; j < 10; j++)			count[j] = 0; //每次分配前清空计数器		for (j = 0; j < n; j++)		{   			k = (data[j] / radix) % 10; //统计每个桶中的记录数			count[k]++;		}		for (j = 1; j < 10; j++)			count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中		{   			k = (data[j] / radix) % 10;			tmp[count[k] - 1] = data[j];			count[k]--;		}		for (j = 0; j < n; j++) //将临时数组的内容复制到data中			data[j] = tmp[j];		radix = radix * 10;	}}

10.3算法分析

基数排序基于分别排序，分别收集，所以是最稳定的。但基数排序的性能略差，每一次关键字都需要O(n)的时间复杂度，而且新的分配之后也需要O(n)。时间复杂度O(n+k)，其中k为桶的数量。