【数据结构】排序详解

数据结构】排序详解"/>

【数据结构】排序详解

排序详解

• 冒泡排序
• 插入排序
• 希尔排序
• 选择排序
• 快速排序
• 归并排序

冒泡排序

其实我们之前就用到过很多次的冒泡排序，它的原理就是相邻的两个元素互换。
我们就想象一下，对于一个初始无序的数组，我们排序第一遍的话（就是从第一个开始，第一个与第二个交换，第二个与第三个交换…第n-1个与第n个交换），这时最大的是不是就到了它合适的位置。下面又是从头开始，只不过这时呢就要排序前n-1个数据了，以此类推，直到还剩两个数据，这时排一遍不就行了嘛。所以我们一共排了n-1回。
现在我们算一下每排一回要比较多少次，排第一回时第一个与第二个比较，一直到第n-1个和第n个比较，这是n-1回，下边还有n-1个数据，这时就比较n-2回，直到最后的1回。

于是我们的代码就有了

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

我们这里的i跟上面说的一样，循环n-1次，j第一回循环n-1次，后面每回减一，正好根据i加一的特性，直接让它减去个i就可以了

插入排序

插入排序我们在生活中用的最多的可能就是摸扑克牌了，我们要在一个有序的牌中插入一个刚摸的牌，是不是要逐个的比较，然后选择合适的位置，这里就是我们的插入排序了。
现在给定一个数组，第一个数据肯定是有序的，从第二个数据开始，进行插入排序，使两个数据有序，再找第三个，以此类推，直到全部有序。
从第二个元素到第n个元素，一共要循环n-1回，我们每次循环，以升序为例，我们先把第i个元素记下来，如果前面的元素大于它，那么前面的数据往后覆盖，直到找到比它小的数据，把它放在这个数据的前面。

然后我们的代码就有了

void InsertSort(int* a, int n) {for (int i = 1; i < n; i++) {int tmp = a[i];int end = i - 1;while (end >= 0) {if (a[end] > tmp) {a[end + 1] = a[end];}else {break;}end--;}a[end + 1] = tmp;}
}

希尔排序

希尔排序其实本质上就是多次的插入排序，多次的插入排序？可能你会觉得它肯定比插入排序慢吧，其实相反，希尔排序在处理大量数据时快的多
我们知道，插入排序在处理较为有序的数据时是比较快的，因为进行插入排序时只要处理的数据比前面要比较的数据大（以升序为例），就跳出循环就行了
所以我们希尔排序的前几步就是预排序的过程，就是把这一堆数据先排成大致有序。具体步骤就是，隔几个值去插入排序，然后逐步减少这个值，最后让这个值等于一，就是我们的插入排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

选择排序

选择排序顾名思义就是一次选出一组数据中最小的那个，把它和第一个交换数据，第一个就排好了，下面找后面中最小的，与第二个交换数据，以此类推，一个一个的就排好了

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

当然一次只选一个最小的确实有些浪费，我们也可以同时选出一个最大的，把最大的放到最后一个位置，这样遍历一次不就放好两个值了嘛，这样效率会更高一下

void SelectSort(int* a, int n) {int start = 0;int end = n - 1;while (start < end) {int maxi = start;int mini = start;for (int i = start + 1; i <= end; i++) {if (a[i] > a[maxi]) {maxi = i;}if (a[i] < a[mini]) {mini = i;}}Swap(&a[start], &a[mini]);if (start == maxi) {maxi = mini;}Swap(&a[end], &a[maxi]);start++;end--;}
}

最后一个if要注意一下，这里为什么要判断呢？因为如果说最大值的下标就为start的话，我们在倒数第二个Swap当中就会把最大值给交换走，此时下标为maxi的数据就不是最大的了，所以我们的maxi要跟着最大值走，最大值被交换到了下标为mini的位置，我们就要改一下maxi

快速排序

快速排序呢，有三个版本，虽然这三个版本的效率变化不大，但都是对于上一个版本的逻辑上的优化，就是使上一个版本更加容易理解和少出错，话不多说，我们来看第一个版本

我们选取一个数组中的第一个元素为一个参考值，其中从数组最左边开始有一个指针往右寻找大于参考值的值，最右边有一个指针开始寻找小于参考值的值，两个都找到后进行交换，最终两个指针相遇，相遇点肯定是小于参考值的，最后让相遇点的值与最左边的参考值交换位置，这样相遇点左边的值就是全部小于参考值的，相遇点右边的值就是全部大于参考值的。
话又说回来，我们怎么让相遇点的值一定小于参考值，那就是，让右边的指针先走，为什么呢？如果说右边的指针是遇到小于参考值的值停下的话，那么左边的指针就会在那与它相遇，如果说是右边的指针去找左边的指针，因为左边的指针刚交换完值是小于参考值的，所以右指针找到的左指针就是小于参考值的。

 void QuickSort1(int* a, int begin, int end) {if (begin >= end) {return;}int keyi = begin;int left = begin;int right = end;while (left < right) {while (a[right] >= a[keyi] && left < right) {right--;}while (a[left] <= a[keyi] && left<right) {left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left + 1, end);}

第二个版本叫做挖坑法，先把最左边的值记录下来，把这个位置当作坑，之后从右边开始找小于参考值的数，找到后把这个数放到坑中，坑就变成了新找到的这个数，在从左边找大于参考值的数，再放到右边的新坑，在让这个位置当作坑，以此类推，直到左边的指针和右边的指针相遇，再让记录下来的值放到最终的这个坑中。

 void QuickSort2(int* a, int begin, int end) {if (begin >= end) {return;}int tmp = a[begin];int pit = begin;int left = begin;int right = end;while (left<right) {while (left < right && tmp <= a[right]) {right--;}Swap(&a[pit], &a[right]);pit = right;while (left < right && tmp >= a[left]) {left++;}Swap(&a[pit], &a[left]);pit = left;}a[pit] = tmp;QuickSort2(a, begin, pit - 1);QuickSort2(a, pit + 1, end);}

归并排序

归并排序也是把数据分开，去分别的使它们有序

 void _MergeSort(int* a, int* tmp, int begin, int end) {if (end <= begin) {return;}int mid = (end + begin) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid+1 , end);int cur = begin;int x1 = begin;int x2 = mid;int x3 = mid+ 1;int x4 = end;while (x1 <= x2 && x3 <= x4) {if (a[x1] < a[x3]) {tmp[cur++] = a[x1++];}else {tmp[cur++] = a[x3++];}}while (x1 <= x2) {tmp[cur++] = a[x1++];}while (x3 <= x4) {tmp[cur++] = a[x3++];}memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));}void MergeSort(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {perror("malloc fail");exit(-1);}_MergeSort(a, tmp, 0, n - 1);free(tmp);}

排序确实是数据结构这门课中非常重要的一环，鉴于我是初学者，对各个排序的理解还是不够深彻，只能先潦草的把这篇博客写完，等我以后理解的更加深彻之后，我肯定会回来完善这篇博客的，话不多说，我先发布了