数据结构

2023-03-11 18:32| 来源: 网络整理| 查看: 265

文章目录插入排序直接插入排序希尔排序选择排序直接选择排序堆排序交换排序冒泡排序快速排序归并排序总结：

插入排序直接插入排序

1.直接插入排序的思想是：认为前n个是有序的将n+1个插入进来，那么将第n+1个的值与前n个进行比较，不停的比直到找到比它小（这里我们默认为排升序）或者是比完了就结束。其实这个更像是打牌摸当我们摸第一张的时候我们默认它有序，但是当我们开始摸第二张的时候我们就和第一张进行比较，找它合适的位置，直接插入排序的适应能力很强，因为数组中就算只有某一段有序或者是接近于有序都是减少比较的次数该排序的时间复杂度毋庸置疑就是O(N2)。请添加图片描述代码如下：

void InsertSort(int* arr, int n) { for (int i = 0; i if (arr[end] > tmp) { arr[end + 1] = arr[end];//更新，让后一个等于前一个 end--; } else { break; } } arr[end + 1] = tmp; } } 希尔排序

2.希尔排序是在直接插入排序前先进行预排序，这个预排序的目的（默认是排升序）是为了实现让大的更快的到后面去，小的更快的到前面去，例如数组的最后一个数字是“最小的数”，那么这个“最小的数” 需要和前面所有数字进行比较才能来到它应该在的位置，该算法的时间复杂度为O（N3/2）,为啥是这么多我无法证明。预排序：将数组分为gap组，每隔gap为一组，然后再对每一组进行排序，例如：

请添加图片描述可以发现，当gap越小时，越接近有序，当gap=1时就是插入排序，但此时数组已经接近有序了，需要比较的次数就会大大减少很多。代码如下：

void ShellSort(int* arr, int n) { int gap=n;//记住这里的gap是间隔多少 while (gap > 1) { gap/= 2;//这里如果是除3，记得一定要＋1，gap=gap/3+1, //因为例如当n=6时这种情况会等于0 for (int i = 0; i if (arr[end] > tmp) { arr[end + gap] = arr[end]; end-=gap;//这里一定是减gap，因为每gap间隔为一组 } else { break; } } arr[end + gap] = tmp;//将tmp还回正确的位置 } } } 选择排序直接选择排序

1.直接选择排序的思想就是通过不停选数达到有序，（默认排升序）选出一个最大的和一个最小的值，最小的最左边的值进行交换，最大的和最右边进行交换，然后左边++，右边–，缩小空间，最后他们要么错位要么在同一个位置停下，达到有序。该算法的时间复杂度是O(N2). 在这里插入图片描述代码如下：

void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* arr, int n) { int left = 0; int right = n - 1; while (left if (arr[mini] >arr[i]) { mini = i; } if (arr[maxi] maxi = mini; } Swap(&arr[right--], &arr[maxi]); } } 堆排序

2.堆排序：这里我们运用的是向下调整的思路，向下调整算法使用是前提是左右子树都是“堆”，堆的概念：所有的父亲都大于孩子叫大堆，所有父亲都小于孩子叫小堆。向下调整最多需要调整高度次。如图：在这里插入图片描述

那么建堆就可以完成了，我们可以从最后一个节点的父亲开始依次往前向下调整，堆就建好了。

//使用条件，左右子树都是堆 void AdjustDown(int* arr, int n, int root) { int parent = root; int child = 2 * parent + 1;//默认左孩子 while (child child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } void HeapSort(int* arr, int n) { //在数组父亲和孩子下标的关系如下 // leftchild=parent*2+1; // rightchild=parent*2+2; // parent=(child-1)/2; //建堆----O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, n, i); } int end = n - 1; for (int i = end; i >= 0; i--) { Swap(&arr[0], &arr[i]); AdjustDown(arr, i, 0); } }

建堆的时间复杂度计算： T(n)=2(h-2)(1)+2(h-3)(2)+2(h-4)(3)+……+20(h-1) 2T(n)=2(h-1)(1)+2(h-2)(2)+2(h-3)(3)+……+21(h-1) 由下减上得 T(n)=2(h-1)+2(h-2)+2(h-3)+…………+2-20(h-1) 整理得 T(n)=20+21+22+…………2(h-3)+2(h-2)+2(h-1)-h 由等比数列求和公式可得 T(n)=2h-1-h(2h-1是等于N) 即T(n)=N-h（h是常数可以忽略不记）所以建堆的时间复杂度为O(N)

排序，排升序建大堆,排降序建小堆(可将第一个与最后一个进行交换，则得到最大的那个数字，将最后一个位置不看做堆里的数字然后向下调整，依次直到数组中只有一个数字就结束；如果是建小堆虽然得到了最小的那个数字，但是堆的结构就被破坏了，那么建堆的意义就没有了)

排序的时间复杂度计算：最坏情况就是每一个数据都需要向下调整高度次，由上可知 2h-1=N,则 ,h=log(N+1)即log(N),所以所有数据需要调整N*logN次，所以堆排的时间复杂度为NlogN+N(O(N)在这里可以忽略不计)，即时间复杂度为NlogN,因此堆排选数的效率很高。

交换排序冒泡排序

1：冒泡排序的思想(排升序)：后一个和前一个比，比它大就进行交换直到冒到最后一个位置，那么最后一个位置就是最大的数据就已经排好了，不看最后一个位置，在进行前面的依次比较，依次类推。冒泡排序应该是这里面最low的一种排序，没有任何的优势，时间复杂度为O(N2)。冒泡排序的单趟如图所示：在这里插入图片描述代码如下：

void BubbleSort(int* arr, int n) { int end= 0; while (end if (arr[i - 1] > arr[i]) { //这里的Swap和上面的一样 Swap(&arr[i - 1], &arr[i]); } } end++; } }

可以看出虽然冒泡和直接插入的时间复杂度都是O(N2)但冒泡是比不上插入的，因为插入排序如有一段或者接近有序都会减少很多的比较量，而冒泡就算差一个就有序也会在那傻乎乎的一个一个的比较。

快速排序

2：思想(假设排升序)首先选一个数作为key，选谁都可以但我们一般选左边第一个数，便于控制。那么选的key在左边那么就是右边先走，为了排升序那么我们单趟要实现的结果就是左边比它小右边比它大，所以右边先走找小，找到小之后停下，左边开始走找到大，找到之后，他们进行交换，当他们相遇时这个相遇点就是key最终应该在的位置那么key就排好了，那么就还有(假设keyi是key的下标)[begin,keyi-1] keyi [keyi+1,end]，那么用分治思想左边进行相同的算法，右边也是运用相同的算法，分治思想进行递归，这里介绍三种常见的方法。 a.Hoare方法，也就是发明快排的那个人，他的想法大概就如上所示，单趟如下动图：在这里插入图片描述

当这个单趟走完时，这个6就已经排好了，这个方法需要注意的是左边作key右边先走，右边做key左边先走。代码实现如下：

void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return; } int left = begin; int right = end; int keyi = begin;//需要处理的那个数字的下标 while (left right--; } while (left int tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return; } int left = begin; int right = end; int key = arr[begin]; int hole = begin; while (left right--; } arr[hole] = arr[right]; hole = right; while (left int tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return; } int cur = begin; int prve = begin; int keyi = begin; while (cur // ++prve; // if (prve != cur) // { // Swap(&arr[prve], &arr[cur]); // } //} //写上面或者下面这种都可以，只是需要注意，遇见小的prve需要先加加一下才能比较 if (arr[cur] int mid = (begin + end) / 2; if (arr[begin] > arr[mid]) { if (arr[mid] > arr[end]) { return mid; } else if (arr[begin] return end; } } else //arr[begin] < arr[mid] { if (arr[mid] return begin; } else { return end; } } } void QuickSort(int* arr, int begin, int end) { if (begin >= end) { return; } //三数取中 int mid = GetMid(arr, begin, end); Swap(&arr[mid], &arr[begin]); int left = begin; int right = end; int keyi = begin;//需要处理的那个数字的下标 if(begin-end+1 while (left right--; } while (left if (left>=right) { return; } int mid = (left+right) / 2; _MergeSort(arr,left, mid, tmp); _MergeSort(arr, mid+1, right, tmp); int begin1 = left, begin2 = mid + 1; int end1 = mid, end2 = right; int index = left; while (begin1 tmp[index++] = arr[begin1++]; } else { tmp[index++] = arr[begin2++]; } } while (begin1 tmp[index++] = arr[begin2++]; } //拷贝回去 for (int i = left; i int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(arr, 0, n - 1, tmp);//当前函数的子函数 free(tmp); return; } 总结：排序方式最好情况最坏情况稳定性直接插入排序O(N)O(N2)稳定希尔排序O(N2/3)O(N2)不稳定直接选择排序O(N2)O(N2)稳定堆排序O(NlogN)O(NlogN)不稳定冒泡排序O(N)O(N2)稳定快速排序O(NlogN)O(N2)不稳定归并排序O(NlogN)O(NlogN)稳定

文章中还有不足的地方，还请各位大佬谅解并指出，谢谢。

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻