排序算法总结（选择、冒泡、插入、希尔、归并、快排、堆排序、桶排序、基数排序、计数排序）

• 选择排序
• 冒泡排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序
• 基数排序
• 计数排序
• 算法性能比较（时间复杂度、空间复杂度及稳定性）

算法描述

图片来自：https://github.com/damonare/Sorts

1. 在一个长度为N的无需数组中，将第1个数的下标设为min。遍历后面N-1个数与min比较，若比min小将其下标重新设为min。遍历结束后将下标为min的数与第一个数交换。
2. 将第2个数的下标设为min。遍历后面N-2个数。遍历结束后将下标为min的数与第二个数交换。
3. 重复以上操作直至遍历N-1次，将下标为min的数与第N-1个数交换。排序完成。

代码实现

class Solution {
public:
	vector selectSort(vector& nums) {
		for(int i = 0; i < nums.size() - 1; i++) {
			int min = i;
			for(int j = i + 1; i < nums.size(); j++) {
				if(nums[j] < nums[min]) {
					min = j;
				}
			}
			if(min != i) {
				swap(nums[i], nums[min]);
			}
		}
		return nums;
	}
};

时间复杂度、空间复杂度及稳定性

• 时间复杂度：
  在任何情况下，选择排序算法都需要遍历 N-1 次，每次遍历需比较的次数分别是 N，N-1，N-2，……，1。在最好的情况下，即数组完全有序时，不需要做任何交换，需要进行 N(N + 1)/2 次操作。在最坏的情况下，即数组逆序时，需要交换次数为N-1次，需要进行 N(N + 1)/2+ N - 1 次操作。
  综上所述，无论是最好的情况还是最差的情况，选择排序的时间复杂度都为O(n²)。
• 空间复杂度：
  O(1)。
• 稳定性：
  不稳定。
  举例：对数组[5，9，5，1，3]进行选择排序，第一次遍历交换1与第一个5的位置，则排序完成后两个5的相对位置有所改变。

算法描述

图片来自：https://github.com/damonare/Sorts

1. 对N个数两两进行比较，顺序相反则交换位置，一次遍历过后最小或最大的数将移至数组末尾。
2. 对前N-1个数重复以上操作。
3. 重复以上操作，N-1次遍历后排序完成。

代码实现

class Solution {
public:
	vector bubbleSort(vector& nums) {
		for(int i = 0; i < nums.size() - 1; i++) {
			bool flag = true;
			for(int j = 0; j < nums.size() - 1 - i; j++) {
				if(nums[j] > nums[j + 1] {
					swap(nums[j], nums[j + 1]);
					flag = false;
				}
			}
			if(flag) {
				break;
			}
		}
		return nums;
	}
};

时间复杂度、空间复杂度及稳定性

• 时间复杂度：
  最好的情况下，即数组完全有序时，需进行一次遍历，比较 N-1 次，不进行交换。最坏的情况下，即数组逆序时，需进行 N-1 次遍历，每次遍历分别进行 N-1，N-2，……，1次交换，需要进行 N(N - 1)/2 次操作。
  综上所述，冒泡排序最好的情况下时间复杂度为O(n)，最坏的情况下时间复杂度为O(n²)，平均时间复杂度为O(n)与O(n²)取平均值，仍然是O(n²)。
• 空间复杂度：
  O(1)。
• 稳定性：
  稳定。

算法描述

图片来自：https://github.com/damonare/Sorts

1. 假设前 i-1 个数已经排好顺序，将第 i 个数插入到前 i-1 个有序数列中，使得前 i 个数成为有序数列。
2. 重复以上操作，总共遍历 n-1 次，排序完成。

代码实现

class Solution {
public:
	vector insertionSort(vecotr& nums) {
		for(int i = 1; i < nums.size(); i++) {
			int j = i;
			while(j > 0 && nums[j] < nums[j - 1]) {
				swap(nums[j], nums[j - 1]);
				j--;
			}
		}
		return nums;
	}
};

时间复杂度、空间复杂度及稳定性

• 时间复杂度：
  最好的情况下，即数组完全有序时，需进行 N-1 次比较，不进行交换。最坏的情况下，即数组逆序，需要进行 N-1 次遍历，每次需要比较的次数分别为 1，2，……，N-1 次，每次比较都需要进行交换。
  综上所述，插入排序最好的情况下时间复杂度为O(n)，最坏的情况下时间复杂度为O(n²)，平均时间复杂度为O(n²)。
  在数组元素随机排列的情况下，插入排序要稍优于上面两种排序。
• 空间复杂度：
  O(1)。
• 稳定性：
  稳定。

算法描述

代码实现
时间复杂度、空间复杂度及稳定性

算法描述

代码实现
时间复杂度、空间复杂度及稳定性

算法描述

代码实现
时间复杂度、空间复杂度及稳定性

算法描述

代码实现
时间复杂度、空间复杂度及稳定性

算法描述

代码实现
时间复杂度、空间复杂度及稳定性

算法描述

代码实现
时间复杂度、空间复杂度及稳定性