数据结构（16）排序（上）

一、插入排序

1.1 直接插入排序

        直接插入排序是一种简单的插入排序法，其基本思想是把待排序的记录按照关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

        比如，现在有一个数组{5,3,9,6,2,4}。我们把{5}看成是一个有序序列，剩下来的{3,9,6,2,4}看成是待排序的序列。我们定义一个变量end，始终指向有序序列的最后一个位置（也就是当前下标为0的位置），也就是这里的数据5。再定义一个临时变量tmp，用来保存end + 1位置的数据（也就是这里的数据3），接着拿tmp和有序序列中的最后一个元素进行比较，5比3大，就把5放到end + 1的位置，end--，此时end越界，end + 1的值为0，把3放到end + 1的位置上去。

//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1;i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

                                         直接插入排序时间复杂度为O(n^2)

1.2 希尔排序

        希尔排序法又称缩小增量法。其基本思想是先选定一个整数（通常是gap = n / 3 + 1），把待排序元素分成若干组，距离相等的元素分在同一组，并对每一组内的元素进行排序，然后gap = gap/3 +1再得到下一个整数，再将数组分组，进行插入排序。希尔排序是对直接插入排序的优化。

        比如，现在有一数组{9,1,2,5,7,4,8,6,3,5}，先按照距离为5的数据为一组。

对每一组数据进行插入排序，得到数组{4,1,2,3,5,9,8,6,5,7}

然后把距离为2的数据划分成一组。

分别对这两组数据进行插入排序，得到数组{2,1,4,3,5,6,5,7,8,9}

最后划分成一组，进行插入排序，得到最终有序的数据。

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//对每组进行直接插入排序for (int i = 0;i < n - gap;i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

二、选择排序

2.1 直接选择排序

每一次从待排序的数据元素中选出最小和最大的元素，分别放在序列的起始和末尾位置，直到全部待排序元素排完。

根据上述思路，我们写出如下的代码：

//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin;i <= end;i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);begin++;end--;}
}

这样的代码看似没有问题，符合我们的思路，但是运行之后发现结果有异常——

那问题出在哪了呢？我们来看下面这张图：

现在我们找到了begin和end组成区间内的最小值4，而4此时出现在的是end的位置；找到了最大值6，此时位于begin的位置。我们拿最小值4和begin位置的6做交换，此时排序结果就已经是我们想要的结果了，但是别忘了还有一句代码，我们拿最大值arr[maxi]和end位置的值做交换，就又把刚才才排好序的4和6又换回来了！然后begin++，end--，跳出循环。就出现了异常的结果。那么现在我们知道问题所在了——最大值刚好出现在了begin的位置（begin == maxi），导致我们找到的最大值被最小值给替换掉了。

修改之后的正确代码如下：

//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin;i <= end;i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}if (maxi == begin){maxi = mini;}Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);begin++;end--;}
}

                                            直接选择排序时间复杂度为O(n^2)

2.2 堆排序

堆排序在前面数据结构（13）堆部分讲的很详细了，这里就不做过多赘述了，要注意排升序建大堆，排降序建小堆。感兴趣的可以看一下我的这篇文章，链接如下：https://blog.csdn.net/seanmooPercy/article/details/149880188?fromshare=blogdetail&sharetype=blogdetail&sharerId=149880188&sharerefer=PC&sharesource=seanmooPercy&sharefrom=from_link

三、交换排序

3.1 冒泡排序

和堆排序一样，冒泡排序在前面部分讲的很详细，这里就不做过多赘述。感兴趣的可以看我写的这篇文章，链接放下面了~https://blog.csdn.net/seanmooPercy/article/details/146456572?fromshare=blogdetail&sharetype=blogdetail&sharerId=146456572&sharerefer=PC&sharesource=seanmooPercy&sharefrom=from_link

重点是下面要讲的排序方法——

3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换方法，其基本思想为：任取待排序元素中的某元素作为基准值，按照该排序编码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中左右元素均大于基准值，然后重复该过程直至排序完成。

快速排序的主框架代码如下：

//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值int keyi = _QuickSort(arr, left, right);//left  keyi  right//左序列[left, keyi - 1]   右序列[keyi + 1, right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

那么，如何实现找基准值的函数_QuickSort呢？我们有以下三种方式：

3.2.1 Hoare版本

代码实现：

//Hoare版本
int _QuickSort(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){//right:从右往左走，找比基准值小的while (left <= right && arr[right] > arr[keyi]){right--;}//left:从左往右走，找比基准值大的while (left <= right && arr[left] < arr[keyi]){left++;}if (left <= right){Swap(&arr[left], &arr[right]);left++;right--;}}Swap(&arr[keyi], &arr[right]);return right;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值int keyi = _QuickSort(arr, left, right);//left  keyi  right//左序列[left, keyi - 1]   右序列[keyi + 1, right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

                                                   时间复杂度为O(NlogN)

注意：当基准值和left/right指向的数据相等时也要交换。因为当数组中的数据全部为重复数据时，会导致时间复杂度由nlogn变为n^2.

3.2.2 挖坑法

思路：创建左右指针。首先从右往左找出比基准值小的数据，找到后立刻放入左坑中，当前位置变成新的坑。然后从左往右找出比基准值大的数据，找到后立刻放入右坑中，当前位置变成新的坑。结束循环后将最开始存储的分界值放入当前坑中，返回当前坑的下标（即分界值下标）。

参考代码：

int _QuickSort(int* arr, int left, int right)
{int hole = left;int key = arr[hole];while(left < right){while(left < right && arr[right] > key){right--;}arr[hole] = arr[right];hole = right;while(left < right && arr[left] < key){left++;}arr[hole] = arr[left];hole = left;}a[hole] = key;return hole;
}

但是这个方法有个很致命的问题，就是不能处理重复的数据，会死循环。但是如果我们吧内层循环条件添加上“=”号就不会死循环，但是快排递归次数可能会变成n^2。所以该方法用的很少，更常用的还是上面讲的Hoare版本和下面的这个方法——

3.2.3 Lomuto前后指针

创建前后指针，从右往左找比基准值小的进行交换，使得小的数据都排在基准值左边。

步骤图如下：

参考代码：

//Lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{int key = left;int prev = left, cur = left + 1;while (cur <= right){if (arr[cur] < arr[key]){prev++;Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[key], &arr[prev]);return prev;
}

3.2.4 非递归版本快速排序

借助数据结构——栈

我们把数组的左右区间压入栈中，然后取栈顶两次，运用Lomuto前后指针法划分左右区间，再让左右区间进栈，重复上面操作，直至栈为空。

//非递归版本快速排序——栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;StackInit(&st);StackPush(&st, left);StackPush(&st, right);while (!StackEmpty(&st)){//取栈顶两次int end = StackTop(&st);StackPop(&st);int begin = StackTop(&st);StackPop(&st);//[begin, end]找基准值int key = begin;int prev = begin, cur = begin + 1;while (cur <= end){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[key], &arr[prev]);key = prev;//begin  key  end//左序列:[begin, key - 1]//右序列:[key + 1, end]if (key + 1 < end){StackPush(&st, key + 1);StackPush(&st, end);}if (begin < key - 1){StackPush(&st, begin);StackPush(&st, key - 1);}}StackDestroy(&st);
}

四、归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是分治算法的一种非常典型的应用。将已经排好序的子序列合并，得到有序的完全序列。若将两个有序表合并成一个有序表，则称二路归并。

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}//[left, right]int mid = (left + right) / 2;//根据mid划分左右两个序列:[left, mid]  [mid + 1, right]_MergeSort(arr, left, mid ,tmp);_MergeSort(arr, mid + 1, right, tmp);//合并两个有序序列int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//[begin1, end1]   [begin2, end2]while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//tmp中有序数据导入到原数组//[left, right]for (int i = left;i <= right;i++){arr[i] = tmp[i];}
}
void MergeSort(int* arr, int n)
{int tmp = (int*)malloc(n * sizeof(int));_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}