七大排序经典排序算法

---

吾日三省吾身：高否？富否？帅否？答曰：否。滚去学习!!!(看完这篇文章先)

目前只有C和C++的功底，暂时还未开启新语言的学习，但是大同小异，语法都差不多。

目录：
一.排序定义
二.排序算法的评价指标(最后总结)
1.算法的稳定性
2.时间复杂度和空间复杂度
三.七大排序算法
1.冒泡排序
2.选择排序
3.插入排序
4.希尔排序
5.归并排序
6.快速排序
7.堆排序
稳定性及其复杂度总结

一.排序定义

排序(sort):排序就是重新排列表中的元素，使得元素满足按关键字有序的过程。

二.排序算法的评价指标(最后总结)

1.算法的稳定性

若待排序表中有两个元素R1和R2，其对应的关键字相同即k1= k2,且在排序前R1在R2的前面，若使用某一排序算法排序后，R1仍然在R2的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

意思就是两个相同的关键字在排序前后位置不变,排序前在前面那么排序前就在前面，后面就在后面。

如果排序前后两个数的位置不相同，那么此算法就是不稳定的。

2.时间复杂度和空间复杂度

三.七大排序算法

·排序算法分为内部排序和外部排序，内部排序的时候哦数据都存储在内存中，外部排序中由于数据过多而无法全部放入内存。

1. 冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

冒泡排序算法步骤：

1. 从数组的第一个元素开始，依次比较每对相邻的元素，如果前面的元素大于后面的元素，就交换它们的位置。

2. 对数组中的每一对相邻元素重复步骤1，直到最后一个元素。此时，数组中最后一个元素应该是最大的元素。

3. 针对除去已排序的最后一个元素的剩余元素，重复步骤1和步骤2，直到整个数组都被排序。

注意：

当输入的数据是正序这个时候排序最快

当输入的数据是反序这个时候排序最慢

C语言实现

#include <stdio.h>
void bubble_sort(int arr[], int len) {int i, j, temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}
int main() {int arr[] = { 2, 4, 6, 8, 5, 7,9 , 1,3,10};int len = (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);return 0;
}

C++实现

#include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {int i, j;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
}
int main() {int arr[] = {2, 4, 6, 8, 5, 7,9 , 1,3,10 };int len = (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;return 0;
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1)

2.选择排序

选择排序（Selection Sort）是一种简单的排序算法。其基本思想是首先从未排序的元素中找到最小的元素，然后将其放到已排序的序列末尾，然后再从剩余未排序的元素中继续找到最小的元素，将其放到已排序的序列末尾，以此类推，直到所有元素都排好序。

选择排序的算法步骤

1. 遍历待排序的数组，从第一个元素开始

2. 在未排序的元素中找到最小的元素，记录其下标

3. 将最小的元素与第一个元素交换位置

4. 接着在未排序的元素中继续寻找最小的元素，记录其下标

5. 将最小的元素与第二个元素交换位置

6. 重复步骤 4-5 直到所有元素都排序完成

C语言实现

void swap(int *a,int *b) //交换两个数
{int temp = *a;*a = *b;*b = temp;
}
void selection_sort(int arr[], int len)
{int i,j;for (i = 0 ; i < len - 1 ; i++){int min = i;for (j = i + 1; j < len; j++)     //走访未排序的元素if (arr[j] < arr[min])    //找到目前最小值min = j;    //记录最小值swap(&arr[min], &arr[i]);    //做交換}
}

C++实现

template<typename T> 
void selection_sort(std::vector<T>& arr) {for (int i = 0; i < arr.size() - 1; i++) {int min = i;for (int j = i + 1; j < arr.size(); j++)if (arr[j] < arr[min])min = j;std::swap(arr[i], arr[min]);}
}

3.插入排序

插入排序（Insertion Sort）排序算法，其思想是从第二个元素开始依次将其插入到已经有序的序列中。

插入排序的算法步骤

1第二个元素开始，将该元素视为一个有序序列。

2将该元素与它前面的元素进行比较，如果前面的元素比它大，则交换位置。

3继续向前比较，直到该元素找到了合适的位置。

4对下一个元素重复上述过程，直到所有元素都排好序为止。

C语言实现

void insertion_sort(int arr[], int len){int i,j,key;for (i=1;i<len;i++){key = arr[i];j=i-1;while((j>=0) && (arr[j]>key)) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

C++实现

void insertion_sort(int arr[],int len){for(int i=1;i<len;i++){int key=arr[i];int j=i-1;while((j>=0) && (key<arr[j])){arr[j+1]=arr[j];j--;}arr[j+1]=key;}
}

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)

4.希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也被称为“缩小增量排序”。它的基本思想是先将待排序的序列分割成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终完成排序。

算法步骤

1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, t k = 1；

2.按增量序列个数 k，对序列进行 k 趟排序；

3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插 入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

C语言实现

void shell_sort(int arr[], int len) {int gap, i, j;int temp;for (gap = len >> 1; gap > 0; gap >>= 1)for (i = gap; i < len; i++) {temp = arr[i];for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)arr[j + gap] = arr[j];arr[j + gap] = temp;}
}

C++实现

template<typename T>
void shell_sort(T array[], int length) {int h = 1;while (h < length / 3) {h = 3 * h + 1;}while (h >= 1) {for (int i = h; i < length; i++) {for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {std::swap(array[j], array[j - h]);}}h = h / 3;}
}

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

5.归并排序

归并排序（Merge Sort）是一种分治算法，其基本思想是将待排序序列分成若干个子序列，分别进行排序，然后将子序列合并成一个有序序列。

归并排序算法步骤：

1. 将待排序序列分成两个子序列，分别进行递归排序。

2. 合并两个有序子序列，得到一个更长的有序序列。

3. 重复上述过程，直到所有子序列都有序。

int min(int x, int y) {return x < y ? x : y;
}
void merge_sort(int arr[], int len) {int *a = arr;int *b = (int *) malloc(len * sizeof(int));int seg, start;for (seg = 1; seg < len; seg += seg) {for (start = 0; start < len; start += seg * 2) {int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}int *temp = a;a = b;b = temp;}if (a != arr) {int i;for (i = 0; i < len; i++)b[i] = a[i];b = a;}free(b);
}

C++实现

template<typename T> 
void merge_sort(T arr[], int len) {T *a = arr;T *b = new T[len];for (int seg = 1; seg < len; seg += seg) {for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++];}T *temp = a;a = b;b = temp;}if (a != arr) {for (int i = 0; i < len; i++)b[i] = a[i];b = a;}delete[] b;
}

C++(递归版)

void Merge(vector<int> &Array, int front, int mid, int end) {// preconditions:// Array[front...mid] is sorted// Array[mid+1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid+1 ... end] to RightSubArrayvector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);int idxLeft = 0, idxRight = 0;LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]for (int i = front; i <= end; i++) {if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {Array[i] = LeftSubArray[idxLeft];idxLeft++;} else {Array[i] = RightSubArray[idxRight];idxRight++;}}
}void MergeSort(vector<int> &Array, int front, int end) {if (front >= end)return;int mid = (front + end) / 2;MergeSort(Array, front, mid);MergeSort(Array, mid + 1, end);Merge(Array, front, mid, end);
}

6.快速排序

快速排序（Quick Sort）是一种常用的排序算法，也是一种分治算法。其基本思想是选择一个基准元素，将待排序序列分成两个子序列，使得一个子序列中所有元素都比基准元素小，另一个子序列中所有元素都比基准元素大，然后递归地对子序列进行排序。

具体实现过程如下：

1. 选择一个基准元素，一般选择第一个元素或者随机选择一个元素。

2. 将序列中所有比基准元素小的元素放在基准元素的左边，所有比基准元素大的元素放在右边。

3. 对基准元素的左右两边重复上述过程，直到每个子序列只剩下一个元素。

C语言实现

typedef struct _Range {int start, end;
} Range;Range new_Range(int s, int e) {Range r;r.start = s;r.end = e;return r;
}void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;
}void quick_sort(int arr[], const int len) {if (len <= 0)return; Range r[len];int p = 0;r[p++] = new_Range(0, len - 1);while (p) {Range range = r[--p];if (range.start >= range.end)continue;int mid = arr[(range.start + range.end) / 2]; int left = range.start, right = range.end;do {while (arr[left] < mid) ++left; while (arr[right] > mid) --right; if (left <= right) {swap(&arr[left], &arr[right]);left++;right--;               }} while (left <= right);if (range.start < right) r[p++] = new_Range(range.start, right);if (range.end > left) r[p++] = new_Range(left, range.end);}
}

C++实现

int Paritition1(int A[], int low, int high) {int pivot = A[low];while (low < high) {while (low < high && A[high] >= pivot) {--high;}A[low] = A[high];while (low < high && A[low] <= pivot) {++low;}A[high] = A[low];}A[low] = pivot;return low;}void QuickSort(int A[], int low, int high) //快排母函数{if (low < high) {int pivot = Paritition1(A, low, high);QuickSort(A, low, pivot - 1);QuickSort(A, pivot + 1, high);}}

7.堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

1创建一个堆 H[0……n-1]；

2把堆首（最大值）和堆尾互换；

3把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

4重复步骤 2，直到堆的尺寸为 1。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>void swap(int *a, int *b) {int temp = *b;*b = *a;*a = temp;
}void max_heapify(int arr[], int start, int end) {// 建立父節點指標和子節點指標int dad = start;int son = dad * 2 + 1;while (son <= end) { // 若子節點指標在範圍內才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的son++;if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數return;else { // 否則交換父子內容再繼續子節點和孫節點比較swap(&arr[dad], &arr[son]);dad = son;son = dad * 2 + 1;}}
}void heap_sort(int arr[], int len) {int i;// 初始化，i從最後一個父節點開始調整for (i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢for (i = len - 1; i > 0; i--) {swap(&arr[0], &arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len = (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);int i;for (i = 0; i < len; i++)printf("%d ", arr[i]);printf("\n");return 0;
}

C++实现

#include <iostream>
#include <algorithm>
using namespace std;void max_heapify(int arr[], int start, int end) {//建立父节点和字节点int dad = start;int son = dad * 2 + 1;while (son <= end) { if (son + 1 <= end && arr[son] < arr[son + 1]) // 比较两个子节点大小，选择大的son++;if (arr[dad] > arr[son]) // 如果父节点大于子节点代表完整，退出函数return;else { swap(arr[dad], arr[son]);dad = son;son = dad * 2 + 1;}}
}void heap_sort(int arr[], int len) {for (int i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);for (int i = len - 1; i > 0; i--) {swap(arr[0], arr[i]);max_heapify(arr, 0, i - 1);}
}int main() {int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };int len = (int) sizeof(arr) / sizeof(*arr);heap_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;return 0;
}

稳定性以及复杂度

大话数据结构关于排序算法的的总结：