从入门到精通数据结构----四大排序(上)

目录

首言：

 1. 插入排序

  1.1 直接插入排序

  1.2 希尔排序

2. 选择排序 

 2.1 直接选择排序  

  2.2 堆排序

3. 交换排序

  3.1 冒泡排序

  3.2 快排 

 结尾：

首言：

    本篇文章主要介绍常见的四大排序：交换排序、选择排序、插入排序、归并排序。上主要介绍前三种。由常见的时间复杂度较大的，再到复杂到较小的比较难的排序。由浅入深，层层递进，实现对排序的深刻理解.

 1. 插入排序

  1.1 直接插入排序

      实现简单的插入排序，需要我们首先进行单趟的排序。其基本思想为：故名思意就是将尾部最后面位置的数插入到比他大的数的前面，并将大的数据向后移动。方法为：找到尾部的值定义为 end + 1，前面的值为 end , 然后进行判断的比较。

     单趟排序实现的代码为将 end 赋值为 n - 2，之后先前进行比较。

void Part_InitSort(int* a, int n)//a 表示一个数组，n 表示这个数组的大小
{//进行单趟的排序，找到末尾位置int end = n - 2;//使它指向数组的倒数第二个int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}//当遇到小于 tmp 的值的时候跳出循环，并且将 end + 1 的位置放上 tmp。a[end + 1] = tmp;
}

    之后将单趟排序放入到整个的排序之中去，从第一个位置开始(先进行比较前面的两个数字)，记录它的下标放到 tmp 里面如果是 tmp 小的话就进行移动。直到这个 n 表示的后面的倒数第二个的时候，实现全部的排序。进行替换的时候循环结束的条件为到 end 减到 0 为止。

void InitSort(int* a, int n)
{//利用单趟插入的排序的想法，进行一个循环的排序int i = 0;for (i = 0; i < n - 1; i++){//从前两个位置开始int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

  1.2 希尔排序

    由于直接插入排序的时间复杂度非常的高。对其进行优化，现在给出这样一个变量 grap 进行划分，不在一个一个的比较，直接比较相差 grap 个数之后的数进行比较(进行预排)，使用预排序可以实现使整个数组，实现接近有序，从而大大减少直接插入排序的次数。如图所示。 

void ShellSort(int* a, int n)
{//首先我们先不考虑 grap 的大小，假设为 3, 就是相当于将前面的位置的 1 换成了 grapint grap = 3;for (int i = 0; i < n - grap; i++){int tmp = a[i + grap];int end = i;while (end >= 0){if (tmp < a[end]){a[end + grap] = a[end];end -= grap;}else{break;}}a[end + grap] = tmp;}//接下来就是对于 garp 的范围进行确定。 
}

    经过大量的实践得到了：当每次 grap = grap / 3 (grap = n);进行的预排序时间复杂度是最好的。

    进行 grap 的选择的时候具有：如果 grap 很大但是跳的很快，但是越不接近有序的特点。所以当不断缩小空间的时候，由于前面的铺垫，会让后面范围小的插入排序进行次数减少。但是希尔排序也具有不稳定的特点。 

    希尔排序进行结束的条件是grap < 1,因为最后一次执行的就是直接插入排序，但是因为接近有序了，所以需要的次数非常的少。

void ShellSort(int* a, int n)
{//进行一次的希尔排序，并不是已经排序好的，是需要不断地去缩小空间，实现排序//int grap = n;while (grap > 1){grap = (grap / 3) + 1;// + 1 是为了保证最后一次始终有 1 for (int i = 0; i < n - grap; i++){int tmp = a[i + grap];int end = i;while (end >= 0){if (tmp < a[end]){a[end + grap] = a[end];end -= grap;}else{break;}}a[end + grap] = tmp;}}
}

2. 选择排序 

 2.1 直接选择排序  

     基本思想：定义一个 tmp(用来进行遍历)，每次都从第一个位置开始，到 end 结束，如果是a[tmp]大于定义的最大的内个,就将 tmp 赋值给最大的那个下标(小的也一样)。找到最大的最小的那个之后，进行交换，交换的时候最小的交换到第一个位置，最小的交换到最后位置。随后进行 end--，begin++。在进行下一步操作。

     注意选择排序的交换的是带有下标的数组元素，不是直接的替换(直接替换的话，会造成数据的串改)。下面这个串代码包括了选择排序与交换函数。

void SelectSort(int* a, int n)
{assert(a);int begin = 0, end = n - 1, i = 0;for (i = begin; i <= end; i++){//需要寻找的是下标int mini = begin, maxi = end;int tmp = begin;for (tmp = begin + 1; tmp <= end; tmp++){if (a[tmp] > a[maxi]){maxi = tmp;}if (a[tmp] < a[mini]){mini = tmp;}}//在同时进行寻找 最大 与 最小 的时候可能会有最大值在第一个位置的情况.//最小值在开始位置时，这不影响。但是最大值在一开始位置就影响。Swap(&a[begin], &a[mini]);//交换了之后，mini 位置 存放的是最大值if (begin == maxi){maxi = mini;}Swap(&a[maxi], &a[end]);end--;begin++;}
}
void Swap(int* a, int* b)
{int* tmp = a;*a = *tmp;*b = *tmp;
}

  2.2 堆排序

    堆排序就是通过建立堆，来进行排序。升序建立建大堆，降序建小堆。 建堆的话需要进行向下调整算法实现大(小)堆。

   1.向下调整算法(以建立大堆为例)：要求左右子树都是小堆，才可以使用向下调整算法。原理是：通过父亲结点跟左右孩子节点进行比较，如果是孩子比父亲大，就需要进行交换，接着向下走。直到父亲结点比所有的孩子都大的时候就停止。

    2.细节：循环结束的条件是，child == n，因为识别的是数组的下标所有的大小都是 n - 1。其次，跟新完父亲结点之后的孩子结点也是需要更新的。最后的退出条件为当父亲节点比所有的孩子结点都要大的时候，就跳出循环，表示大堆已经建立。

void AdjustDown(int* a, int n, int parent)
{int Child = parent * 2 + 1;//找到左孩子.//当孩子不小于n就停止while (Child < n){if (Child + 1 < n && a[Child] < a[Child + 1])//找到孩子里面最大的一个{Child += 1;}if (a[parent] < a[Child]){Swap(&a[parent], &a[Child]);parent = Child;Child = parent * 2 + 1;}else//因为下面的就都是符合条件的,不需要在进行向下调整.{break;}}
}

2.通过这个算法，在底部从下往上开始进行排序，实现大堆的建立。建立完大堆之后将第一个位置的值放到最后一个位置。排序 n - 1个数。

注意事项：1.建立大堆是需要从最后一个父亲结点，向前进行向下调整算法。2. 注意 i 的范围是从 （n - 1 - 1）/ 2开始的 . 3. 下一次进来的时候，是去排序 end  个数字。

//堆排序的时间复杂度为 n * log(n)
void HeapSort(int* a, int n)
{//堆排序，建立升序用大堆。所以需要一个向下调整函数。//1.首先先建立一个大堆.int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//2.将第一个位置的最大值，放到堆的最后int end = n - 1;while (end >= 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}	
}

3. 交换排序

  3.1 冒泡排序

    冒泡排序是最简单的交换排序，从第一个位置开始向后进行一次交换，直到找到了不符合条件的那个数字，就停止。

    注意实现：i 表示的是进行多少次的交换，主要看的是的 j ，每次都是从 0，第一个位置开始进行计算，比较的是两个数字，所以是 n - 1，但是每次当放到最后的一个位置的时候，会少一个数字，所以每次都要- i；

void BubbleSort(int* a, int n)
{assert(a);int i = 0, j = 0;for (i = 0; i < n ; i++){for (j = 0; j < n - 1- i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

  3.2 快排 

     快速排序是经常会考到，他的主要做法为定义 begin 和 end(倒数第二个数字),最后一个数字 key,begin 去找到比 key 大的数然后停下来，end 去找比 key 小的数然后停下来。之后再进行交换比 key 大的值，与比 key 小的值。当 begin = end 的时候将 key 放到这个位置。

1. 首先先实现单趟的排序。

//函数的left 与 right 区间为；[left, right]
int PartSort1(int* a, int left, int right)
{//选择一个 key，我选择的是最后的位置，所以就需要让 left 进行先走int key = a[right];while (left < right){//左边 去寻找最大的while (left < right && a[left] <= key){left++;}//右边 去寻找最小的while (left < right && a[right] >= key){right--;}//每次进行寻找，找到了 left 指向了较大的， right 指向较小的。就进行交换Swap(&a[left], &a[right]);}//结束循环时表示 left 与 left 相遇到了一起。随便与 k 进行交换可。Swap(&a[key], &a[right]);return left;//叫替换了的位置返回，方便后续进行拆分
}

2. 通过单趟排序，实现整体的快速排序。主要思想是：通过递归让左右都实现有序，不断的向下分直到不能分为止，也就是只有一个数，left 跟 right 都是在一起的时候，表明这个一段数组是有序的。 

void QuickSort(int* a, int left, int right)
{//每次都进行循环，结束条件为左指针遇上了右指针.if (left >= right){return;}//每次递归都划分为两个区域，left - div - 1,div + 1 - right;int div = PartSort2(a, left, right);//进行左边的排序QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);
}

3. 细节：(1) 选定后面的值一定是从最前面的开始进行计算。因为前面去找的是最大的值，需要将最大的值放到后面，如果是右边先走的话，就不是将最小的值放到后面，因此 div 的右边就不是都大于 div 的。 

 (2) 当最后一次进行交换的时候会将 key 位置放到想要的位置，它的前面都是小于 key 的，后面都是大于 key 的。

(3) 其次当对于一个有序的数组直接的进行排序的话复杂度非常的高为：O(n2)，所以需要进行取中间值，避免最后取到 key 的是极值的情况。这个取中间值的方法只要是运用在了进行部分的快速排序算法当中去。让 key 位置是保证为中间值，不是极值。

int MidInit(int* a, int begin, int end)
{int mid = (begin + end )/2;if (a[begin] > a[mid]){if (a[begin] < a[end]){return begin;}else if (a[mid] > a[end]){return mid;}else{return end;}}else //这种情况表示的是 a[begin] < a[mid]{if (a[begin] > a[end]){return begin;}else if (a[mid] > a[end]){return mid;}else{return end;}}
}

(4) 快速排序，还有另外的两种方法：挖坑法 与 前后指针法，以及再进行优化。这个一节我放到下一篇文章中进行讲解。

 结尾：

     如果对你有帮助还请帮我点个免费的赞，支持一下我，我也会不断地改进争取写出跟高质量的文章。我们共同努力！！！！😊😊😊