数据结构初阶(c语言)-排序算法

        数据结构初阶我们需要了解掌握的几种排序算法(除了直接选择排序，这个原因我们后面介绍的时候会解释)如下：

        其中的堆排序与冒泡排序我们在之前的文章中已经详细介绍过并对堆排序进行了一定的复杂度分析，所以这里我们不再过多介绍。

一，插入排序 

1.1直接插入排序 

1.1.1概念及实现代码 

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

       就像我们玩扑克牌一样，当我们将发给我们的牌拿到我们自己手中进行排序一样，当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时用array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。实现代码如下：

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 (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

       从实现代码中我们不难看出， 直接插入的思想为先将前两个元素排好，再一个一个的往后进行，如果后面数据比我们上一次排好的数据的末尾数据大时，让末尾数据后移，再与末尾数据的前一个数据进行比较，直到找到小于的数据为止。插入的方法思想可以类比下我们顺序表中的头插法。

1.1.2复杂度的计算 

        空间复杂度由于未创建辅助空间，所以为O(1)。时间复杂度从代码中我们可以得知，最好情况下为O(N)(数组本身即为顺序)，最坏的情况下(即数组逆序的情况下)为O(N^2)。所以直接插入的时间复杂度为O(N^2)。

1.2希尔排序

 1.1.1概念及实现代码 

       希尔排序是对直接插入排序的改良，再原有的排序方式上加入预排序，以达到减小时间复杂度的目的，实现代码如下：

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;}}
}

        希尔排序一般先将原有数组分为三份，不断的三分对每份里面的数据进行排序，到了最后gap为1时数组已经基本有序，但我们不能直接设gap=n/3，比如我们的数组有效元素个数为9个，分三次之后为0，但我们需要让它的最后一次为一，所以我们的gap每次循环都设置为除三加以，从而确保最后进入循环的gap值为一。

1.1.2复杂度的简要计算

        空间复杂度与直接插入一致为O(1)。而时间复杂度对于外层(预排序)，我们可以联想树，一直三分其实时间复杂度就为树的深度h=logn。所以外层的时间复杂度为logn。对于内层的时间复杂度，博主智商有限，难以推出，因为它的gap能够取得的值太多了，从而导致内层的复杂度难以计算，所以我们直接给出希尔排序的粗略时间复杂度的估算：O(N^1.3)。需要详细推理过程的读者可以自行上网搜寻。

二，选择排序

        这一部分我们不细讲，堆排序上篇文章已经详细介绍过，直接选择排序给出代码我们即可理解其思想：

void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for(int i = begin;i <= end;i++){if (arr[max] < arr[i]){max = i;}if (arr[min] > arr[i]){min = i;}}if (max == begin){max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}
}

        它的思想是逐步的将数据向中间集拢，第一遍找数组中的最大(小)值，并将最大(小)值分别放到头尾，接着让头++尾--。再次重复第一次的操作，最后直到没有数据为止。 

        可见直接选择排序，无论是最好的情况顺序还是最坏的情况逆序，他的时间复杂度均为O(N^2)。在实际学习与生产过程中都不可能使用，这也是我们简略介绍的原因。

三，快速排序 

         快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均子于基准值，右子序列中所有元素均⼤于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

         其实快速排序最主要的思想即为基准值，无限的二分去寻找基准值，与我们前面学习的二叉树非常类似。所以它的递归版本基础框架为(key为我们每次寻找到的基准值)：
 

void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}int key = _QuickSort3(arr, left, right);QuickSort(arr, left, key - 1);QuickSort(arr, key + 1, right);
}

3.1hoare版本快排

          hoare版本的思想为，开始设首数据为基准值，同时设左右指针，左边先找比基准值大的数据，找到停下，右边找比基准值小的数据，停下后于左指针的数据交换，循环下去，直到左指针的对应数组下标小于右指针截止。实现代码如下：

int _QuickSort1(int* arr, int left, int right)
{int key = left;++left;while (left <= right){while (left <= right && arr[left] < arr[key]){left++;}while (left <= right && arr[right] > arr[key]){right--;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}Swap(&arr[right], &arr[key]);return right;
}

          为什么left=right时还要进入循环，是因为每次我们交换完后，right--,left++。万一此时它们正好重合，此处数据若小于或大于基准值都会导致最终基准值的落脚点错误。

3.2挖坑版本快排

          创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准⼤的数据，找到后立即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）。实现代码如下：

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

          这里我们不需要去考虑left与right的相等的情况，因为我们最终基准值的位置与hole相关，所以不会影响我们基准值的落脚点正确。

3.3lomuto前后指针版本

           创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。实现代码如下：

int _QuickSort3(int* arr, int left, int right)
{int key = left;int slow = left;int fast = left + 1;while (fast <= right){if (arr[fast] < arr[key] && ++slow != fast){Swap(&arr[fast], &arr[slow]);}fast++;}Swap(&arr[slow], &arr[key]);return slow;
}

3.4非递归版本的快排框架 

           由于每次我们的快排对基准值的寻找都需要上一次的基准值给出首尾位置，这里我们就可以借助我们之前学习到的堆的知识来进行首尾位置的记录：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void STInit(Stack* ps)
{assert(ps);ps->top = ps->capacity = 0;ps->arr = NULL;
}void DestoryST(Stack* ps)
{assert(ps);assert(ps->arr);free(ps->arr);ps->capacity = ps->top = 0;
}void STpush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int exchange = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* new = (STDataType*)realloc(ps->arr, sizeof(STDataType) * exchange);if (new == NULL){perror("new:");exit(1);}ps->arr = new;ps->capacity = exchange;}ps->arr[ps->top++] = x;
}void STDelt(Stack* ps)
{assert(ps);assert(!EmptyST(ps));--ps->top;
}STDataType EleSTop(Stack* ps)
{assert(ps && !EmptyST(ps));return ps->arr[ps->top - 1];
}int EmptyST(Stack* ps)
{assert(ps);return (ps->top == 0);
}
void QuickSortNone(int* arr, int left, int right)
{Stack st;STInit(&st);STpush(&st, right);STpush(&st, left);while (!EmptyST(&st)){int begin = EleSTop(&st);STDelt(&st);int end = EleSTop(&st);STDelt(&st);int meet = _QuickSort3(arr, begin, end);if (begin < meet - 1){STpush(&st, meet-1);STpush(&st, begin);}if (end > meet + 1){STpush(&st, end);STpush(&st, meet+1);}}DestoryST(&st);
}

        这里我们使用之前文章所给出的堆的实现方法来实现我们的非递归版本的快排的基本架构，这样及做到了减少时间复杂度，又减少了空间复杂度。

3.5复杂度的计算

        快速排序由于是以二叉树的方式进行栈的创建与销毁，所以其空间复杂度为logn，时间复杂度则与我们之前的向下建堆的时间复杂度一致为O(NlogN)。

四，归并排序

         归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divide and Conquer）的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 归并排序核心步骤：

初始数组:

初始未排序数组是 [10, 6, 7, 1, 3, 9, 4, 2]。

1. 分解阶段（自顶向下）:

   • 数组被递归地分解成更小的子数组，直到每个子数组包含一个元素。
   • 第一次分解：[10, 6, 7, 1] 和 [3, 9, 4, 2]。
   • 第二次分解：
     • [10, 6, 7, 1] 分解为 [10, 6] 和 [7, 1]。
     • [3, 9, 4, 2] 分解为 [3, 9] 和 [4, 2]。
   • 第三次分解：
     • [10, 6] 分解为 [10] 和 [6]。
     • [7, 1] 分解为 [7] 和 [1]。
     • [3, 9] 分解为 [3] 和 [9]。
     • [4, 2] 分解为 [4] 和 [2]。

2. 合并阶段（自底向上）:

   • 分解到最小子数组后，开始两两合并，并在合并过程中进行排序。
   • 第一次合并：
     • [10] 和 [6] 合并为 [6, 10]。
     • [7] 和 [1] 合并为 [1, 7]。
     • [3] 和 [9] 合并为 [3, 9]。
     • [4] 和 [2] 合并为 [2, 4]。
   • 第二次合并：
     • [6, 10] 和 [1, 7] 合并为 [1, 6, 7, 10]。
     • [3, 9] 和 [2, 4] 合并为 [2, 3, 4, 9]。
   • 第三次合并：
     • [1, 6, 7, 10] 和 [2, 3, 4, 9] 合并为 [1, 2, 3, 4, 6, 7, 9, 10]

图示如下：

 

实现归并排序的代码如下：

void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_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;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++];}for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

五，各类排序算法的时间及空间复杂度的比较

5.1对于稳定性的解释 

         稳定性的概念在排序算法中指的是如果两个元素在原始数组中有相同的值，那么在排序完成后，它们的相对顺序是否保持不变。

5.1.1稳定排序算法

一个稳定的排序算法会保持相同值的元素在原数组中的相对顺序。例如，考虑以下数组：

[5a, 3, 4, 5b, 2]

在这里，5a 和 5b 是两个相同值的元素，但它们是不同的个体。

如果使用稳定的排序算法（例如冒泡排序或插入排序），那么排序后的数组可能是：

[2, 3, 4, 5a, 5b]

注意，5a 仍然在 5b 之前，这保持了它们在原始数组中的相对顺序。

5.1.2不稳定排序算法

一个不稳定的排序算法则不保证相同值的元素在排序后的相对顺序。例如，考虑同样的数组：

[5a, 3, 4, 5b, 2]

如果使用不稳定的排序算法（例如选择排序或快速排序），那么排序后的数组可能是： 

[2, 3, 4, 5b, 5a]

在这里，5a 和 5b 的相对顺序被改变了。