讨论各种排序（sort）函数，全网最全的排序函数总结

大家好，欢迎来到IT知识分享网。

讨论各种排序（sort）函数，全网最全的排序函数总结

冒泡排序

作为排序函数中最拉胯，但是最简单的函数，冒泡排序对于每个刚刚接触计算机的学生来说都是常用的，这里也是展示一下下面展示一些 内联代码片。

下面展示一些 内联代码片。

// A code block 

// 每次选出当前序列的最大值，选择n - 1次后就会排序成功 void BublleSort(int* arr, int n) { 
    for (int i = 0; i < n - 1; i++) { 
    for (int j = 0; j < n - 1 - i; j++) { 
    if (arr[j] > arr[j + 1]) Swap(arr + j, arr + j + 1); } } } 

堆排序

// A code block void AjustDown(int* arr,int parent); void HeapSort(int* arr,int n); 

//建立一个升序的堆排序，这里应该建立大堆 void AjustDown(int* arr, int n, int parent) { 
    int child = 2 * parent + 1; while (child < n) { 
    if (child + 1 < n && arr[child + 1] > arr[child]) child++;//建立大堆应该找到大的孩子 if (arr[child] > arr[parent]) Swap(arr + child, arr + parent); else break;//大于孩子节点说明当前的节点的位置正确 parent = child; child = 2 * child + 1; } } void HeapSort(int* arr, int n) { 
    //通过向下调整建立大堆，复杂度尾o(n) int end = n - 1; for (int i = (n - 2) / 2; i >= 0; i--) { 
    AjustDown(arr, n, i); } //调整的堆排序 while (end > 0) { 
    Swap(arr, arr + end); AjustDown(arr, end, 0); end--; } } 

选择排序

选择排序是在一次循环中找到最大值和最小值，并进行首位替换,这里替换时存在一些细节，在代码批注中有着相关的展示，对于选择排序，因为其时间复杂度和冒泡接近，因此了解即可

下面展示一些 内联代码片。

// A code block void SelectSort(int* arr,int n); 

// An highlighted block void SelectSort(int* arr, int n) { 
    int begin = 0; int end = n - 1;//每次选出最大值和最小值进行插入 //这里我们找的是下标 while (begin < end) { 
    int min = begin; int max = end; for (int i = begin; i <= end; i++) { 
    if (arr[i] < arr[min]) min = i; if (arr[i] > arr[max]) max = i; } Swap(arr + begin, arr + min); if (max == begin) max = min; Swap(arr + end, arr + max); begin++; end--;//可能出现那种交换重复的可能 //存在需要debug的很多情况 } } 

插入排序

在讲希尔排序之前，我们需要先了解插入排序，因为希尔排序其实就是优化版本的插入排序

下面展示一些 内联代码片。

// A code block void SelectSort(int* arr,int n); 

// An highlighted block void SelectSort(int* arr, int n) { 
    int begin = 0; int end = n - 1;//每次选出最大值和最小值进行插入 //这里我们找的是下标 while (begin < end) { 
    int min = begin; int max = end; for (int i = begin; i <= end; i++) { 
    if (arr[i] < arr[min]) min = i; if (arr[i] > arr[max]) max = i; } Swap(arr + begin, arr + min); if (max == begin) max = min; Swap(arr + end, arr + max); begin++; end--;//可能出现那种交换重复的可能 //存在需要debug的很多情况 } } 

插入排序就是找到end的位置，并从后面一次插入数据，每次插入时找到位置后插入，时间复杂度为o(n^2)，但相比于冒泡和选择在同级别中有着明显的优势

希尔排序（ShellSort）

// A code block void ShellSort(int* arr,int n); 

// An highlighted block void ShellSort(int* arr, int n) { 
    int gap = n; while (gap > 1) { 
    gap /= 2;//在gap取定后，后面的排序方式和插入排序一致 for (int i = 0; i < n - gap; i++) { 
    int end = i; int temp = arr[end + gap]; while (end >= 0) { 
    if (arr[end] > temp) { 
    arr[end + gap] = arr[end]; } else { 
    break; } end -= gap; } arr[end + gap] = temp; } } } 

快排（QuickSort)在计算机的库函数中，几乎所有的排序都是采用的快排，这里我们详细的讲解三种快排的方式。

快排，最好的理解方式，就是将选定的key的位置设为基点，然后将数组分为左边的数组和key和右边数组，通过递归的方式将数组排序（这里他的实质就是将数组建立成一个堆其中对于其中的任意子树中，都能保障左子树<root<右子树）
1.Heare大神的最传统的代码形式，但是其中有很多的需要注意的细节
下面展示一些 内联代码片。

// A code block var foo = 'bar'; 

// An highlighted block //快排的huare版本 //快排的精髓就是建立左边小于root小于右边的堆 int GetMid(int* arr, int left, int right) { 
    int mid = (left + right) / 2; if (arr[left] < arr[mid]) { 
    if (arr[mid] < arr[right]) return mid; else { 
    if (arr[right] > arr[left]) return right; else return left; } } else { 
    if (arr[mid] > arr[right]) return mid; else { 
    if (arr[left] > arr[right]) return right; else return left; } } } void QuickSort(int* arr, int left, int right) { 
    if (left >= right) return;//一个元素时退出 keyi 86 int int begin = left; int end = right; int keyi = GetMid(arr, left, right); //由于如果keyi的值越接近当前中间值，时间复杂度越接近于n*logn //这里采用三数取中,三数取中的即在left和right和mid中找到中间的值，并与left交换，使得更合乎的逻辑 Swap(arr + left, arr + keyi); keyi = left; //这理当right先走的话最后总会走到left的位置与left相遇，因此相遇的位置 //必定是小于arr[keyi]的 while (left < right) { 
    while (left < right && arr[right] >= arr[keyi]) right--; while (left < right && arr[left] <= arr[keyi]) left++; if (left != right) Swap(arr + left, arr + right); } Swap(arr + keyi, arr + left); //left小于right的条件是为了保障在移动时不会越界 QuickSort(arr, begin, left - 1); QuickSort(arr, right + 1, end); } //快排挖坑法 //基本理论就是通过cur去寻找大的右子树值并将其插入左边,相对于heare排序方法跟简单理解和操作 

// A code block var foo = 'bar'; 

// An highlighted block void QuickSort2(int* arr, int left, int right) { 
    if (left >= right) return; int keyi = GetMid(arr, left, right); Swap(arr + keyi, arr + left); keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { 
    if (arr[cur] < arr[keyi]) { 
    prev++; Swap(arr + prev, arr + cur); } cur++; } Swap(arr + keyi, arr + prev); keyi = prev; QuickSort2(arr, left, keyi - 1); QuickSort2(arr, keyi + 1, right); } //通过循环实现快速排序 

// A code block void QuickSortNonR(int* arr,int left,int right); 

// An highlighted block void QuickSortNonR(int* arr, int left, int right) { 
    ST st; STInit(&st); STPush(&st, right); STPush(&st, left); while (!STEmpty(&st)) { 
    int begin = STTop(&st); int end = STTop(&st); if (begin < end) { 
    int keyi = GetMid(arr, begin, end); Swap(arr + begin, arr + keyi); keyi = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { 
    if (arr[cur] < arr[keyi]) { 
    prev++; Swap(arr + prev, arr + cur); } cur++; } Swap(arr + keyi, arr + prev); keyi = prev; STPush(&st, end); STPush(&st, keyi + 1); STPush(&st, keyi - 1); STPush(&st, begin); } } STDestroy(&st); }