• 八大排序详解(默认升序)

    目录

    一、直接插入排序

    二、希尔排序

    三、选择排序 

    四、冒泡排序 

    五、堆排序

    六、快速排序 

    一、三数取中优化 

    二、递归优化 

    三、非递归版 

    四、三路划分优化

    七、归并排序

     八、计数排序

    一、直接插入排序

    直接插入排序：直接插入排序就是像打扑克牌一样，每张牌依次与前面的牌比较，遇到比自己大的就将大的牌挪到后面，遇到比自己小的就把自己放在它后面(如果自己最小就放在第一位)，所有牌排一遍后就完成了排序。

    代码如下： 

    1. // 插入排序
    2. void InsertSort(int* a, int n)
    3. {
    4. 	for (int i = 0; i < n; ++i)
    5. 	{
    6. 		int tmp = a[i];
    7. 		int end = i - 1;
    8. 		while (end >= 0)
    9. 		{
    10. 			if (tmp < a[end])
    11. 			{
    12. 				a[end + 1] = a[end];
    13. 				end--;
    14. 			}
    15. 			else
    16. 			{
    17. 				break;
    18. 			}
    19. 		}
    20. 		a[end + 1] = tmp;
    21. 	}
    22. }

    总结：直接插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)，具有稳定性(相对位置不变)，在接近升序的情况下效果最好，接近O(n)。

    二、希尔排序

    希尔排序：直接插入排序在接近有序的情况下很快，所以就想到在直接插入排序之前先预排序，让数据接近有序，再用直接插入排序，效果就会提升，这就是希尔排序。

    预排序: 先将数据分成 gap 组，每组里面使用直接插入排序。 

    当gap为1时，就是直接插入排序。

     代码如下: 

    1. // 希尔排序
    2. void ShellSort(int* a, int n)
    3. {
    4. 	int gap = n;
    5. 	while (gap > 1)
    6. 	{
    7. 		gap = gap / 3 + 1;//控制gap，最后一次是1
    8. 		for (int i = 0; i < n; i++)
    9. 		{
    10. 			int tmp = a[i];
    11. 			int end = i - gap;
    12. 			while (end >= 0)
    13. 			{
    14. 				if (tmp < a[end])
    15. 				{
    16. 					a[end + gap] = a[end];
    17. 					end -= gap;
    18. 				}
    19. 				else
    20. 				{
    21. 					break;
    22. 				}
    23. 			}
    24. 			a[end + gap] = tmp;
    25. 		}
    26. 	}
    27. }

    总结：希尔排序时间复杂度不好计算，根据教科书，为O(n^1.3)，空间复杂度为O(1)，因为预排序，希尔排序不稳定，也因为预排序，希尔排序在接近有序(无论升序或降序)时，速度最快。

    三、选择排序 

    选择排序：类似打牌，选择排序就是在 所有牌中选出最小的放在最左边，选出最大的放在最右边，然后再从剩余的牌中重复此操作。

    需要注意的是当最大的牌在最左边时，若先与最小的牌交换位置，则会造成错误，只要加个判断调整即可。

     代码如下：

    1. // 选择排序
    2. void SelectSort(int* a, int n)
    3. {
    4. 	int begin = 0, end = n - 1;
    5. 	while (begin < end)
    6. 	{
    7. 		int min = begin, max = begin;
    8. 		for (int i = begin; i <= end; ++i)
    9. 		{
    10. 			if (a[min] > a[i])
    11. 				min = i;
    12. 			if (a[max] < a[i])
    13. 				max = i;
    14. 		}
    15. 		swap(&a[min], &a[begin]);
    16. 		if (a[begin] == a[max])
    17. 			max = min;
    18. 		swap(&a[max], &a[end]);
    19. 		begin++;
    20. 		end--;
    21. 	}
    22. }

    总结：时间复杂度为O(n^2)，空间复杂度为O(n)，不具有稳定性(因为与第一张牌交换时可能会改变相对位置)。

    四、冒泡排序 

    冒泡排序： 遇到比自己小的就交换，每趟冒泡都可以把最大的值放到后面，次大的值放到倒数第二位.....然后结束。

    代码如下： 

    1. void BubbleSort(int* a, int n)
    2. {
    3. 	for (int i = 0; i < n - 1; ++i)
    4. 	{
    5. 		int flag = 0;
    6. 		for (int j = 0; j < n - i - 1; ++j)
    7. 		{
    8. 			if (a[j] > a[j + 1])
    9. 			{
    10. 				swap(&a[j], &a[j + 1]);
    11. 				flag = 1;
    12. 			}
    13. 		}
    14. 		if (flag == 0)
    15. 			break;
    16. 	}
    17. }

     总结：时间复杂度为O(n^2)，空间复杂度为O(n)，具有稳定性。

    五、堆排序

    请看这里(づ￣ 3￣)づ：堆排序与TopK问题-CSDN博客 

    六、快速排序 

     快速排序：选一个key，将小于key的排在左边，大于key的排在右边，排完后key就在有序时的对应位置。

    然后递归左区间和右区间，每个数都在对应位置就能使整体有序。

    让 key 在有序时的对应位置，有三种方法。(小指的是比key小，大就是比key大)

    hoare版本：最老的版本，右边找小，左边找大，找到交换，重复操作到 left >= right 再将 left 与 key 位置的值交换

     挖坑法：key看作坑，右边找小，找到交换，右边看作坑，左边找大，找到交换，左边再看作坑，依次循环，最后坑就在相应位置。

    双指针法：一个cur指针，一个prev指针，cur遇到小就与++prev位置交换，遇到大就cur++，

    使prev位置是小的最后一个。

    代码如下：

    1. // 快速排序hoare版本
    2. int PartSort1(int* a, int left, int right)
    3. {
    4. 	int key = left;
    5. 	while (left < right)
    6. 	{
    7. 		//必须先右再左，若先左再右则要交换left+1的位置
    8. 		//前面加一个left<right防止越界，后面不加等号可能会导致死循环
    9. 		while (left < right && a[right] >= a[key])
    10. 			right--;
    11.  
    12. 		while (left < right && a[left] <= a[key])
    13. 			left++;
    14. 		swap(&a[left], &a[right]);
    15. 	}
    16. 	swap(&a[key], &a[left]);
    17. 	return left;
    18. }

    1. / 快速排序挖坑法
    2. int PartSort2(int* a, int left, int right)
    3. {
    4. 	int hole = left;
    5. 	while (left < right)
    6. 	{
    7. 		while (left < right && a[right] >= a[hole])
    8. 			right--;
    9. 		swap(&a[hole], &a[right]);
    10. 		hole = right;
    11.  
    12. 		while (left < right && a[left] <= a[hole])
    13. 			left++;
    14. 		swap(&a[hole], &a[left]);
    15. 		hole = left;
    16. 	}
    17. 	return hole;
    18. }
    1. // 快速排序前后指针法
    2. int PartSort3(int* a, int left, int right)
    3. {
    4. 	int key = left;
    5. 	int prev = left, cur = prev + 1;
    6. 	while (cur <= right)
    7. 	{
    8. 		if (a[cur] < a[key] && ++prev != cur)
    9. 		{
    10. 			swap(&a[cur], &a[prev]);
    11. 		}
    12. 		cur++;
    13. 	}
    14. 	swap(&a[key], &a[prev]);
    15. 	return prev;
    16. }

    排好一个位置，然后递归左右区间排剩余位置，最终使所有数据有序。

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	if (left >= right)
    4. 		return;
    5.  
    6. 	//int key = PartSort1(a, left, right);
    7. 	//int key = PartSort2(a, left, right);
    8. 	int key = PartSort3(a, left, right);
    9. 	QuickSort(a, left, key - 1);
    10. 	QuickSort(a, key + 1, right);
    11. }

    一、三数取中优化 

     快排在数据接近有序时会出现剩余数据全在右区间的情况，此时最慢，时间复杂度为O(n^2)

    所以我们可以加一个优化：三数取中。就可以极大地规避这种可能性。

    三数取中：加一个三数取中的函数，在left，right，(left+right)/2 这三个位置中选出大小在中间的那个位置做key.

    以hoare版本为例

    1. int GetMid(int* a, int left, int right)
    2. {
    3. 	int mid = (left + right) / 2;
    4. 	if (a[left] > a[right])
    5. 	{
    6. 		if (a[right] > a[mid])
    7. 			return right;
    8. 		else
    9. 		{
    10. 			if (a[left] > a[mid])
    11. 				return mid;
    12. 			else
    13. 				return left;
    14. 		}
    15. 	}
    16. 	else
    17. 	{
    18. 		if (a[left] > a[mid])
    19. 			return left;
    20. 		else
    21. 		{
    22. 			if (a[mid] > a[right])
    23. 				return right;
    24. 			else
    25. 				return mid;
    26. 		}
    27. 	}
    28. }
    29.  
    30. // 快速排序hoare版本
    31. int PartSort1(int* a, int left, int right)
    32. {
    33. 	int mid = GetMid(a, left, right);
    34. 	swap(&a[mid], &a[left]);
    35. 	int key = left;
    36. 	while (left < right)
    37. 	{
    38. 		//必须先右再左，若先左再右则要交换left+1的位置
    39. 		//前面加一个left<right防止越界，后面不加等号可能会导致死循环
    40. 		while (left < right && a[right] >= a[key])
    41. 			right--;
    42.  
    43. 		while (left < right && a[left] <= a[key])
    44. 			left++;
    45. 		swap(&a[left], &a[right]);
    46. 	}
    47. 	swap(&a[key], &a[left]);
    48. 	return left;
    49. }

    二、递归优化 

    在递归左右区间时，根据我们学过的满二叉树知识，最后一层的结点几乎占全部的 50% ，倒数第二层大概占 25% 依次类推，而且最后的小区间是接近有序的，所以我们可以判断区间里的数据个数，若小于10，则用直接插入排序直接排完，可以减少80%多栈的调用。 

    1. void QuickSort(int* a, int left, int right)
    2. {
    3. 	if (left >= right)
    4. 		return;
    5. 	if (right - left + 1 <= 10)
    6. 	{
    7. 		InsertSort(a + left, right - left + 1);
    8. 		return;
    9. 	}
    10. 	//int key = PartSort1(a, left, right);
    11. 	//int key = PartSort2(a, left, right);
    12. 	int key = PartSort3(a, left, right);
    13. 	QuickSort(a, left, key - 1);
    14. 	QuickSort(a, key + 1, right);
    15. }

    三、非递归版 

    非递归版 ：用栈模拟函数栈帧的调用过程

    1. // 快速排序 非递归实现
    2. void QuickSortNonR(int* a, int left, int right)
    3. {
    4. 	stack<int> st;
    5. 	st.push(right);
    6. 	st.push(left);
    7. 	while (!st.empty())
    8. 	{
    9. 		int begin = st.top();
    10. 		st.pop();
    11. 		int end = st.top();
    12. 		st.pop();
    13. 		int key = PartSort3(a, begin, end);
    14.  
    15. 		if (key - 1 < begin)//区间有效入栈
    16. 		{
    17. 			st.push(key - 1);
    18. 			st.push(begin);
    19. 		}
    20. 		
    21. 		if (key + 1 < end)//区间有效入栈
    22. 		{
    23. 			st.push(end);
    24. 			st.push(key + 1);
    25. 		}
    26. 	}
    27. }

    四、三路划分优化

    在有大量重复数据的情况下，我们上面写的快排性能就会快速下降，到O(n^2)。

    为了解决这个问题，我们可以做三路划分优化。

    三路划分：原本的思路是将数据变成左边小于key，右边大于key。

    为了解决大量重复数据的情况，可以将数据划分为  小于key  等于key  大于key。

    1、用一个cur指向 left+1 位置(因为key就是left位置的值)，遍历。

    2、遇到

          (因为 left 位置的值一定为 key ，所以不用再次判断，直接++cur走)

    3、遇到 >key 就交换 right 与 cur 位置的值，把大于的值放右边，然后--right；

          (因为此时 right 所表示的值不确定是等于还是小于 key 所以 cur 不动，在判断一次)

    4、等于 key 时，直接++cur

    5、当 cur > right 时，所有数据遍历完成，结束循环，三路划分结束。

    通过三路划分，我们可以把数据分为   小于key   等于key   大于key  三个区间

      begin = 开始位置, end = 结束位置 [begin, left-1]  [left, right] [right+1, end]

    三路划分结束后我们只要排小于key的区间和大于key的区间即可

    上面时排好了一个key，三路划分是排好所有等于key的数。

    代码如下：

    1. void QuickSort2(int* a, int left, int right)
    2. {
    3. 	if (left >= right)
    4. 		return;
    5.     if (right - left + 1 <= 10)
    6. 	{
    7. 		InsertSort(a + left, right - left + 1);
    8. 		return;
    9. 	}
    10.     
    11.     //三路划分
    12. 	int keyi = GetMid(a, left, right);//三数取中
    13. 	swap(&a[keyi], &a[left]);
    14. 	int key = a[left];
    15. 	int begin = left, end = right;
    16. 	int cur = left + 1;
    17. 	while (cur <= right)
    18. 	{
    19. 		if (a[cur] < key)
    20. 		{
    21. 			swap(&a[cur], &a[left]);
    22. 			cur++; left++;
    23. 		}
    24. 		else if (a[cur] > key)
    25. 		{
    26. 			swap(&a[cur], &a[right]);
    27. 			right--;
    28. 		}
    29. 		else
    30. 			cur++;
    31. 	}
    32.  
    33.  
    34. 	QuickSort2(a, begin, left - 1);//再递归小于key区间
    35. 	QuickSort2(a, right + 1, end);//大于key区间
    36. }

      如果要过力扣的数组排序题，还要在三数取中里面mid换成取随机值！   

      总结：时间复杂度O(nlogn)，空间复杂度O(logn)，不稳定(找到key合适的位置后要交换)

    七、归并排序

     归并排序：大家都做过两个有序数组归并到一起然后整体有序的题目吧，这就是归并排序的核心思路，它先将整个数组递归成一个一个的，然后再不断归并，最后整体有序。就相当于后序遍历的思路，左边有序，右边有序，归并自己，然后自己就有序。

     

    1. void _MergeSort(int* a, int* tmp, int left, int right)
    2. {
    3.     //只有一个数就返回
    4. 	if (left >= right)
    5. 		return;
    6. 	int mid = (left + right) / 2;
    7. 	_MergeSort(a, tmp, left, mid);
    8. 	_MergeSort(a, tmp, mid+1, right);
    9.     //两个数组有序，归并到整体有序
    10. 	int begin1 = left, end1 = mid;
    11. 	int begin2 = mid + 1, end2 = right;
    12. 	int j = begin1;
    13. 	while (begin1 <= end1 && begin2 <= end2)
    14. 	{
    15. 		if (a[begin1] < a[begin2])
    16. 		{
    17. 			tmp[j++] = a[begin1];
    18. 			begin1++;
    19. 		}
    20. 		else
    21. 		{
    22. 			tmp[j++] = a[begin2];
    23. 			begin2++;
    24. 		}
    25. 	}
    26. 	while (begin1 <= end1)
    27. 	{
    28. 		tmp[j++] = a[begin1];
    29. 		begin1++;
    30. 	}
    31. 	while (begin2 <= end2)
    32. 	{
    33. 		tmp[j++] = a[begin2];
    34. 		begin2++;
    35. 	}
    36.     //拷贝回对应位置
    37. 	memcpy(a+left, tmp+left, sizeof(int) * (right - left + 1));
    38. }
    39.  
    40. void MergeSort(int* a, int n)
    41. {
    42. 	int* tmp = (int*)malloc(sizeof(int) * n);
    43. 	_MergeSort(a, tmp, 0, n - 1);
    44. }

    非递归版本： 这个思路就是两两归并，四四归并，八八归并....最后整体有序，所以就可以设置一个gap从1到n，让数据模拟上述过程，循环归并。注意的是要考虑数据不足越界情况。

    1. void MergeSortNonR(int* a, int n)
    2. {
    3. 	int* tmp = (int*)malloc(n * sizeof(int));
    4. 	int gap = 1;
    5. 	while (gap < n)
    6. 	{
    7. 		for (int i = 0; i < n; i += 2*gap)
    8. 		{
    9.             //利用gap设置区间
    10. 			int begin1 = i, end1 = i + gap - 1;
    11. 			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    12. 			//考虑越界情况
    13. 			if (begin2 >= n)//第二组越界就没必要归并了
    14. 				break;
    15. 			if (end2 >= n)//begin2没越，end2越界，修正end2
    16. 				end2 = n - 1;
    17.             //归并
    18. 			int j = i;
    19. 			while (begin1 <= end1 && begin2 <= end2)
    20. 			{
    21. 				if (a[begin1] < a[begin2])
    22. 				{
    23. 					tmp[j++] = a[begin1];
    24. 					begin1++;
    25. 				}
    26. 				else
    27. 				{
    28. 					tmp[j++] = a[begin2];
    29. 					begin2++;
    30. 				}
    31. 			}
    32. 			while (begin1 <= end1)
    33. 			{
    34. 				tmp[j++] = a[begin1];
    35. 				begin1++;
    36. 			}
    37. 			while (begin2 <= end2)
    38. 			{
    39. 				tmp[j++] = a[begin2];
    40. 				begin2++;
    41. 			}
    42. 			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    43. 		}
    44. 		gap *= 2;
    45. 	}
    46. }

    总结： 时间复杂度O(nlogn)，空间复杂度O(n)，稳定。缺点是空间复杂度过高，优势是可以在磁盘中排序（外排序）

     八、计数排序

    计数排序：计数排序是类似哈希表，先开一个数组，让每个值都有一个对应位置，遍历数据，遇到就在对应位置++，最后遍历数组输出。

     代码如下：

    1. void CountSort(int* a, int n)
    2. {
    3. 	//assert(n>0);
    4.     //找到最大值与最小值，为映射做准备
    5. 	int max = a[0], min = a[0];
    6. 	for (int i = 1; i < n; ++i)
    7. 	{
    8. 		if (a[i] < min)
    9. 			min = a[i];
    10. 		if (a[i] > max)
    11. 			max = a[i];
    12. 	}
    13. 	int range = max - min + 1;
    14.     
    15. 	int* Count = (int*)calloc(range, sizeof(int));
    16. 	if (Count == NULL)
    17. 	{
    18. 		perror("calloc fail");
    19. 		exit(-1);
    20. 	}
    21.     
    22.     //对应位置++
    23. 	for (int i = 0; i < n; ++i)
    24. 	{
    25. 		Count[a[i] - min]++;
    26. 	}
    27. 	int j = 0;
    28. 	for (int i = 0; i < range; ++i)
    29. 	{
    30.         //把对应位置写回原数组
    31. 		while (Count[i]--)
    32. 		{
    33. 			a[j++] = i + min;
    34. 		}
    35. 	}
    36. }

    总结 ：计数排序的时间复杂度为O(max(range, n))，空间复杂度为O(range)，稳定。适用于数据集中在某一范围的时候。

    感谢大家观看，欢迎指出错误(๑•̀ㅂ•́)و✧ 

  • 相关阅读:
    权重衰减----添加正则化(多层感知机)
    集合框架：List系列集合：特点、方法、遍历方式、ArrayList,LinkList的底层原理
    【centos7安装ElasticSearch】
    单区域OSPF配置
    【毕业设计】基于大数据的电影数据爬取分析可视化系统
    思福迪 运维安全管理系统 test_qrcode_b 远程命令执行漏洞
    DAC实验(DAC 输出三角波实验)(DAC 输出正弦波实验)
    Redis_第二章_实战篇_第一节_ 短信登录
    95、Spring Data Redis 之使用RedisTemplate 实现自定义查询 及 Spring Data Redis 的样本查询
    CyberSploit:1
  • 原文地址：https://blog.csdn.net/m0_74626010/article/details/133579503