C/C++ 数据结构与算法【排序】 常见7大排序详细解析【日常学习，考研必备】带图+详细代码

常见7种排序算法

• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 希尔排序（Shell Sort）
• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• 堆排序（Heap Sort）

算法复杂度

1、冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换位置。这个过程持续对数列的末尾进行，直到整个数列都排序完成。

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

/* 冒泡排序 */
void BubbleSort(int arr[], int len) // arr： 需要排序的数组； length： 数组长度 注： int cnt = sizeof(a) / sizeof(a[0]);获取数组长度
{for (int i = 0; i < len; i++){for (int j = 0; j < len -  i - 1; j++){if (arr[j] > arr[j + 1]){int temp;temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}
}

2、选择排序

选择排序是一种简单直观的排序算法，其基本原理是每一次从待排序的数组里找到最小值（最大值）的下标，然后将最小值（最大值）跟待排序数组的第一个进行交换，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。反复的进行这样的过程直到待排序的数组全部有序。

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

// 自定义方法：交换两个变量的值
void swap(int *a,int *b) 
{int temp = *a;*a = *b;*b = temp;
}
/* 选择排序 */
void SelectSort(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]);    //做交换/*if (index != i)  // 不用自定义函数时可以用选择下面方式进行交换{temp = arr[i];arr[i] = arr[index];arr[index] = temp;}*/}
}

3、插入排序

插入排序是一种简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

例如要将数组arr = [4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。

无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

插入排序算法的原理如下：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后；

6.重复步骤2~5。

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

/* 插入排序 */
void InsertSort(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;}
}

4、希尔排序

希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。

逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。

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

//希尔排序
void ShellSort(int arr[], int len)
{int gap = len;while (gap > 1){//每次对gap折半操作gap = gap / 2;//单趟排序for (int i = 0; i < len - gap; ++i){int end = i;int tem = arr[end + gap];while (end >= 0){if (tem < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}
}

5、归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子 序列中只有一个数据时），就对子序列进行归并。

归并指的是把两个排好序的子序列合并成一个 有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

（1）递归实现归并排序

// 合并两个子数组函数
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int* L = (int*)malloc(n1 * sizeof(int));int* R = (int*)malloc(n2 * sizeof(int));// 将数据复制到临时数组L[]和R[]for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并临时数组回到arr[left..right]int i = 0; // 初始化第一个子数组的索引int j = 0; // 初始化第二个子数组的索引int k = left; // 初始化合并子数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制L[]剩余的元素，如果有while (i < n1) {arr[k] = L[i];i++;k++;}// 复制R[]剩余的元素，如果有while (j < n2) {arr[k] = R[j];j++;k++;}free(L);free(R);
}// 归并排序函数
void merge_sort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 对每一半进行排序merge_sort(arr, left, mid);merge_sort(arr, mid + 1, right);// 合并排好序的两半merge(arr, left, mid, right);}
}

（2）非递归实现归并排序

// 非递归实现归并排序
void mergeSortIterative(int arr[], int size) {int* temp = (int*)malloc(size * sizeof(int));if (temp == NULL) {printf("Memory allocation failed\n");return;}for (int width = 1; width < size; width *= 2) {for (int i = 0; i < size; i += 2 * width) {int left = i;int mid = (i + width < size) ? i + width - 1 : size - 1;int right = (i + 2 * width - 1 < size) ? i + 2 * width - 1 : size - 1;merge(arr, temp, left, mid, right);}}free(temp);
}

6、快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分 为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。

[ 比基准值小的数] 基准值 [比基准值大的数]

接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据 进行排序时同样也会使用快速排序

void QuickSort(int array[], int low, int high) {int i = low; int j = high;if(i >= j) {return;}int temp = array[low];while(i != j) {while(array[j] >= temp && i < j) {j--;}while(array[i] <= temp && i < j) {i++;}if(i < j) {swap(array[i], array[j]);}}//将基准temp放于自己的位置，（第i个位置）swap(array[low], array[i]);QuickSort(array, low, i - 1);QuickSort(array, i + 1, high);
}

7、堆排序

堆排序是一种树形选择排序算法，它的基本思想是将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。

堆排序是一种基于堆数据结构的排序算法，它的时间复杂度为O(nlogn)。

堆的概念
集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1（左节点） 且 Ki<=K2i+2（右节点），则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。完全二叉树（除了最后一层以外上面的节点但是非空的，最后一层节点是从左到右依次排布的）

堆的性质
1.堆中某个节点的值总是不大于或不小于其父节点的值;
2.堆总是一棵完全二叉树。

完全二叉树
完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

完全二叉树的第 i 层至多有 2^i - 1 个结点。
完全二叉树的第 i 层至少有 2^(i - 1) 个结点。
完全二叉树的叶子结点只出现在最底层和次底层。
完全二叉树每一层的结点个数都达到了最大值

（1）大顶堆

（2）小顶堆

//向下调整算法（要满足它下面的都满足堆，才能用）
void AdjustDown(int* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]) child+=1;//把他移到右孩子那里if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;}
}堆排序
void HeapSort(int* arr, int n)
{//建大堆//从最后一个根开始，就相当于它下面的都满足堆，就可以用向下调整算法for (int i = (n-1-1)/2; i >= 0; i--)//n-1-1是因为数组的最后一个元素下标是n-1{AdjustDown(arr, n, i);}//排序for (int i = n; i > 1; i--){swap(&arr[0],&arr[i - 1]);AdjustDown(arr, i-1, 0);}
}