十大经典排序算法_十大排序算法时间复杂度

十大经典排序算法

目录

十大经典排序算法

1.时间复杂度为O(n2)

1.1.冒泡排序（Bubble Sort）

1.2.选择排序（Selectin Sort）

1.3.插入排序（Insertion Sort）

1.4.希尔排序（Shell Sort）

2.时间复杂度为O(nlogn)   

2.1.快速排序（Quick Sort）

2.2.归并排序（Merge Sort）

2.3.堆排序（HeapSort）

3.时间复杂度为线性

3.1.计数排序（Counting Sort）

3.2.基数排序（radix sort）

3.3.桶排序（Bucket Sort）

---

根据算法的时间空间复杂度列出以下10种排序算法，其中蓝色底的为稳定排序，绿色底的为不稳定排序。

先谈一谈稳定性：稳定性简单来讲就是考虑排序后值相同的元素和排序前是否保持一致（如排序前a1和a2值相同，排序后仍是a1在前a2在后）

注：希尔排序时间复杂度在O(nlogn)~O(n2）之间

根据时间复杂度来划分成三小类排序

1.时间复杂度为O(n2)

1.1.冒泡排序（Bubble Sort）

简单的思想：数组中相邻元素两两比较[以左边大为例子，交换两者的位置]；每一次遍历都会将最大的元素下沉到数组的后端，总共遍历n-1轮，所以需要时间复杂度为O(n2)

具体实现：

void bubbleSort(vector<int>& a)
{
	int len = a.size();
	for (int i = 0; i < len - 1; i++) //需要循环次数
	{
		for (int j = 0; j < len - 1 - i; j++) //每次需要比较个数
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]); //交换
			}
		}
	}
}

1.2.选择排序（Selectin Sort）

简单的思想：首先在未排序序列中找到最小元素(也可以是最大的），存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小的元素，然后放到已排序的后面

具体实现：

void selectionSort(vector<int> &a)
{
    int len = a.size();
    for (int i = 0, minIndex; i < len - 1; i++) //需要循环次数
    {
        minIndex = i;                     //最小下标
        for (int j = i + 1; j < len; j++) //访问未排序的元素