• 【C语言之排序】-------六大排序

                                                              作者主页：作者主页

                                                              数据结构专栏：数据结构

                                                             创作时间 ：2024年5月18日

    前言：

    今天我们就给大家带来几种排序的讲解，包括冒泡排序，插入排序，希尔排序，选择排序，堆排序，快速排序等等，在讲解之前我先给大家一个网站，用于查看各种排序的动图，这样有助于我们更加清晰的去了解各种排序：排序动图

    冒泡排序：

    首先我们来讲解一下冒泡排序，这是我们学习编程第一个接触到的排序，也是较为容易理解的一个排序，下面我们来看一下她是如何实现的。

    这就是一个大概的冒泡排序的实现过程，其实就是每次都把最大的一个放到最后面，然后下一轮就不需要去管后面最大的那几个。

    下面我们来看一下代码应如何实现：

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. void print(int* arr, int n) 
    7. {
    8.     for (int i = 0; i < n; i++) 
    9.     {
    10.         printf("%d ", arr[i]);
    11.     }
    12. }
    13.  
    14. int main() 
    15. {
    16.     int arr[] = { 23,235,13,123523,2342,2342,1,41523,3456,6547,546 };
    17.  
    18.     int n = sizeof(arr) / sizeof(arr[0]);
    19.     for (int i = 0; i < n - 1; i++)
    20.     {
    21.         for (int j = 0; j < n - 1 - i; j++) 
    22.         {
    23.             if (arr[j] > arr[j + 1]) {  
    24.                 swap(arr[j], arr[j + 1]);
    25.             }
    26.         }
    27.     }
    28.     print(arr, n);
    29.  
    30.     return 0;
    31. }

    这就是冒泡排序实现的过程，这里我们就不过多的去说了，还是比较简单的。

    时间复杂度：最坏情况：O(N^2)
          最好情况：O(N)
    空间复杂度：O(1)

    插入排序：

    下面我们来看一下插入排序，插入排序的步骤大概是这样的。

    1.从第一个元素开始，该元素可以认为已经被排序
    2.取下一个元素tem，从已排序的元素序列从后往前扫描
    3.如果该元素大于tem，则将该元素移到下一位
    4.重复步骤3，直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
    6.重复步骤2~5

    图像演示：

    这个图像还是比较清晰易懂的，下面我们来看一下代码吧。

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

    插入排序其实就是我们从第一个开始，然后我们用tmp记录要被插入的元素，然后一直和前面的作比较，如果大于前面的，那么就结束，如果小于前面的，我们就令end+1的位置等于end，然后end--就可以了，最后再将temp放到不符合这个条件的位置，就完成了一轮插入排序，后面也是这样循环进行的。

    时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
          最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
    空间复杂度：O(1)

    希尔排序：

    下面我们来讲一下希尔排序，这个排序其实是比较难懂的，但他的时间复杂度也是较为小的，下面我们看一下如何实现这个排序：

    大致步骤：

    1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
    2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

    代码：

    1. void ShellSort(int* arr, int n)
    2. {
    3.     int gap = n;
    4.     while (gap > 1)
    5.     {
    6.         gap /= 2;
    7.         for (int i = 0; i < n - gap; i++)
    8.         {
    9.             int end = i;
    10.             int temp = arr[end + gap];
    11.             while (end >= 0)
    12.             {
    13.                 if (temp < arr[end])
    14.                 {
    15.                     arr[end + gap] = arr[end];
    16.                     end -= gap;
    17.                 }
    18.                 else
    19.                 {
    20.                     break;
    21.                 }
    22.             }
    23.             arr[end + gap] = temp;
    24.         }
    25.     }
    26. }

    时间复杂度平均：O(N^1.3)
    空间复杂度：O(1)

    选择排序：

    思路：

    每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
    实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

    下面我们来看一下动图：

    这里我们图片仅供参考，因为我们要用两个下标，一个最大值，一个最小值，以此来提高效率。

    1. void SelectSort(int* arr, int n)
    2. {
    3.     int begin = 0, end = n - 1;
    4.     while (begin < end)
    5.     {
    6.         int max = begin, min = begin;
    7.         for (int i = begin; i <=end; i++)
    8.         {
    9.             if (arr[i] < arr[min])
    10.             {
    11.                 min = i;
    12.             }
    13.             if (arr[i] > arr[max])
    14.             {
    15.                 max = i;
    16.             }
    17.         }
    18.         swap(arr[begin], arr[min]);
    19.         //为防止最大值在begin位置被换走，我们还要加个判断
    20.         if (begin == max)
    21.         {
    22.             max = min;
    23.         }
    24.         swap(arr[max], arr[end]);
    25.         ++begin;
    26.         --end;
    27.     }
    28. }

     时间复杂度：最坏情况：O(N^2)
          最好情况：O(N^2)
    空间复杂度：O(1)

    堆排序：

    想要更好的了解堆排可以查看这篇博文：堆

    在学习堆排之前，首先我们要知道社么是堆，堆其实就是一个二叉树，然后有大根堆和小根堆，然后他们分别长这样：

    然后我们这里排序的思路就是，比如说大根堆，他的最大值一定在堆顶，然后我们就让他和最后一个数交换，然后不再去管他，再得到一个新的大根堆，继续进行这个操作，这样是不是就实现了呢。

    然后这里我们首先还要建堆，然后我们升序的话就建大堆，直接把最大的放在最后一个，然后就不把他看作堆里的数据了。反之，降序就建小堆。下面我们先来看一下如何建堆。

    1. //向上调整(小根堆)
    2. void AdjustUp(HPDataType* a, int child)
    3. {
    4. 	int parent = (child - 1) / 2;
    5. 	while (child>0)
    6. 	{
    7. 		//if (a[child] < a[parent])//小于就换就相当于建小堆
    8. 		if (a[child] > a[parent])//大于就换就会变成大堆
    9. 		{
    10. 			std::swap(a[child], a[parent]);
    11. 			child = parent;
    12. 			parent = (child - 1) / 2;
    13. 		}
    14. 		else
    15. 		{
    16. 			break;
    17. 		}
    18. 	}
    19. }
    20.  
    21.  
    22.  
    23. //建堆
    24. void HPPush(HP* php, HPDataType x)
    25. {
    26. 	assert(php);
    27.  
    28. 	if (php->size == php->capacity)
    29. 	{
    30. 		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    31. 		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
    32. 		if (tmp == NULL)
    33. 		{
    34. 			perror("realloc failed!!!");
    35. 			return;
    36. 		}
    37. 		php->a = tmp;
    38. 		php->capacity = newcapacity;
    39. 	}
    40.  
    41. 	php->a[php->size++] = x;
    42.  
    43. 	//向上调整
    44. 	AdjustUp(php->a, php->size - 1);
    45. }

    这就是c语言种建堆的一个过程，还是比较麻烦的。

    然后有了堆之后，排序就比较简单了。

    1. void HeapSort(int* a, int n)
    2. {
    3. 	//首先建堆
    4. 	//升序：建大堆
    5. 	//降序：建小堆
    6. 	/*for (int i=0;i
    7. 	{
    8. 		AdjustUp(a, i);
    9. 	}*/
    10. 	//            求最后一个节点的父亲
    11. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    12. 	{
    13. 		AdjustDown(a, n, i);
    14. 	}
    15.  
    16. 	int end = n - 1;
    17. 	///这里>0即可，因为=0时只剩下最后一个，就不再需要继续进行了
    18. 	while (end>0)//思路就是：比如我们升序排序，那么我们就利用大根堆，每次都将最大的那个数放在最顶上，然后将它和最后一个交换，然后让整体的大小--，那么最后一个就不再会受影响
    19. 	{
    20. 		std::swap(a[0], a[end]);
    21. 		AdjustDown(a, end, 0);
    22. 		--end;
    23. 	}
    24.  
    25.  
    26. }

    堆排最好的最坏的时间复杂度均为O(n*logn)

    空间复杂度为O(1)

    快速排序：

    快排还是这几个排序种比较麻烦的有一个，但其实也是比较好用的一个

    我们这里将会用三种方法来实现这个快速排序：

    hoare版本(左右指针法)：

    思路：
    1、选出一个key，一般是最左边或是最右边的。
    2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
    3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
    4.此时key的左边都是小于key的数，key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

    1. //快速排序   hoare版本(左右指针法)
    2. void QuickSort(int* arr, int begin, int end)
    3. {
    4. 	//只有一个数或区间不存在
    5. 	if (begin >= end)
    6. 		return;
    7. 	int left = begin;
    8. 	int right = end;
    9. 	//选左边为key
    10. 	int keyi = begin;
    11. 	while (begin < end)
    12. 	{
    13. 		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    14. 		while (arr[end] >= arr[keyi] && begin < end)
    15. 		{
    16. 			--end;
    17. 		}
    18. 		//左边选大
    19. 		while (arr[begin] <= arr[keyi] && begin < end)
    20. 		{
    21. 			++begin;
    22. 		}
    23. 		//小的换到右边，大的换到左边
    24. 		swap(&arr[begin], &arr[end]);
    25. 	}
    26. 	swap(&arr[keyi], &arr[end]);
    27. 	keyi = end;
    28. 	//[left,keyi-1]keyi[keyi+1,right]
    29. 	QuickSort(arr, left, keyi - 1);
    30. 	QuickSort(arr,keyi + 1,right);
    31. }

    挖坑法：

    递归：

    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
    2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

    1. //快速排序法  挖坑法
    2. void QuickSort1(int* arr, int begin, int end)
    3. {
    4. 	if (begin >= end)
    5. 		return;
    6. 	int left = begin,right = end;
    7. 	int key = arr[begin];
    8. 	while (begin < end)
    9. 	{
    10. 		//找小
    11. 		while (arr[end] >= key && begin < end)
    12. 		{
    13. 			--end;
    14. 		}
    15. 		//小的放到左边的坑里
    16. 		arr[begin] = arr[end];
    17. 		//找大
    18. 		while (arr[begin] <= key && begin < end)
    19. 		{
    20. 			++begin;
    21. 		}
    22. 		//大的放到右边的坑里
    23. 		arr[end] = arr[begin];
    24. 	}
    25. 	arr[begin] = key;
    26. 	int keyi = begin;
    27. 	//[left,keyi-1]keyi[keyi+1,right]
    28. 	QuickSort1(arr, left, keyi - 1);
    29. 	QuickSort1(arr, keyi + 1, right);
    30. }
    非递归：
    1. //单趟排
    2. int PartSort(int* arr, int begin, int end)
    3. {
    4. 	int key = arr[begin];
    5. 	while (begin < end)
    6. 	{
    7. 		while (key <= arr[end] && begin < end)
    8. 		{
    9. 			--end;
    10. 		}
    11. 		arr[begin] = arr[end];
    12. 		while (key >= arr[begin] && begin < end)
    13. 		{
    14. 			++begin;
    15. 		}
    16. 		arr[end] = arr[begin];
    17. 	}
    18. 	arr[begin] = key;
    19. 	int meeti = begin;
    20. 	return meeti;
    21. }
    22.  
    23. void QuickSortNoR(int* arr, int begin, int end)
    24. {
    25. 	stack<int> st;
    26. 	//先入右边
    27. 	st.push(end);
    28. 	//再入左边
    29. 	st.push(begin);
    30. 	while (!st.empty())
    31. 	{
    32. 		//左区间
    33. 		int left = st.top();
    34. 		st.pop();
    35. 		//右区间
    36. 		int right = st.top();
    37. 		st.pop();
    38. 		//中间数
    39. 		int mid = PartSort(arr, left, right);
    40. 		//当左区间>=mid-1则证明左区间已经排好序了
    41. 		if (left < mid - 1)
    42. 		{
    43. 			st.push(mid - 1);
    44. 			st.push(left);
    45. 		}
    46. 		//当mid+1>=右区间则证明右区间已经排好序
    47. 		if (right > mid + 1)
    48. 		{
    49. 			st.push(right);
    50. 			st.push(mid + 1);
    51. 		}
    52. 	}
    53. }

    前后指针法：

    思路：
    1、选出一个key，一般是最左边或是最右边的。
    2、起始时，prev指针指向序列开头，cur指针指向prev+1。
    3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作

    1. //快速排序法  前后指针版本
    2. void QuickSort2(int* arr, int begin, int end)
    3. {
    4. 	if (begin >= end)
    5. 		return;
    6. 	int cur = begin, prev = begin - 1;
    7. 	int keyi = end;
    8. 	while (cur != keyi)
    9. 	{
    10. 		if (arr[cur] < arr[keyi] && ++prev != cur)
    11. 		{
    12. 			swap(&arr[cur], &arr[prev]);
    13. 		}
    14. 		++cur;
    15. 	}
    16. 	swap(&arr[++prev],&arr[keyi]);
    17. 	keyi = prev;
    18. 	//[begin,keyi -1]keyi[keyi+1,end]
    19. 	QuickSort2(arr, begin, keyi - 1);
    20. 	QuickSort2(arr, keyi + 1, end);
    21.  
    22. }
  • 相关阅读:
    手动开平方数（结果为整数）-2022
    scipy实现单因素方差分析
    12 - DEM故障处理分析
    效率提升 100%，YRCloudFile 让自动驾驶安全更有保障
    2023年最新一面二面通关王炸java八股文面试题--持续更新
    [游戏] C++ chat
    GP规范--PUTKEY
    组合类替换嵌套内置类型实现多层嵌套业务
    TypeScript基础
    ML：机器学习工程化之团队十大角色背景、职责、产出物划分之详细攻略
  • 原文地址：https://blog.csdn.net/bhbcdxb123/article/details/139462289