当前位置：首页 > ds >正文

数据结构-排序

ds 2025/7/5 23:28:08

一、排序的基本概念

排序是将一组元素按照某种规律排列成一个序列的过程。排序主要分为内部排序（数据在内存中完成排序）和外部排序（数据量过大，需借助外部存储完成排序）。常用排序算法有插入类、交换类、选择类、归并类和分配类等。

二、插入类排序

直接插入排序

基本思想：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

算法步骤：

从第一个元素开始，认为已排序序列初始为空。
取下一个元素，与已排序序列中的元素依次比较，找到插入位置。
将元素插入到正确的位置。

示意：假设初始序列为49,38,65,97,76,13,27。排序过程如下：

第一趟：插入38到49前面，序列变为38,49,65,97,76,13,27。
第二趟：插入65保持在49后面，序列不变。
第三趟：插入97保持在65后面，序列不变。
第四趟：插入76到65和97之间，序列变为38,49,65,76,97,13,27。
第五趟：插入13到38前面，序列变为13,38,49,65,76,97,27。
第六趟：插入27到38前面，序列变为13,27,38,49,65,76,97。

折半插入排序

基本思想：在直接插入排序的基础上，使用折半查找法确定插入位置。

算法步骤：

确定插入位置时，使用折半查找减少比较次数。
将元素插入到正确的位置。

希尔排序

基本思想：将整个序列分成多个子序列分别进行直接插入排序，子序列的初始步长较大，逐渐减小到1。

算法步骤：

选择一个增量序列，如dt,dt−1,…,d1=1。
按增量序列分组，对每组使用直接插入排序。
逐渐减小增量，直到增量为1，完成排序。

示意图：初始序列13,14,94,33,82,25,59,94,65,23,45,27,73,25，增量取5：

第一组：13,25,65,25，排序后13,25,65,25。
第二组：14,59,23,73，排序后14,23,59,73。
第三组：94,82,94,45，排序后82,94,94,45。
第四组：33，不变。
增量减为1时，整个序列进行直接插入排序，得到最终有序序列。

三、交换类排序

冒泡排序

基本思想：通过比较相邻元素，将较大的元素逐步“冒泡”到序列末尾。

算法步骤：

从序列开始，依次比较相邻元素，若前者大于后者则交换。
每一轮将最大的未排序元素冒泡到末尾。
重复直到整个序列有序。

示意：初始序列49,38,65,97,76,13,27：

第一轮：比较并交换，最大元素97到末尾，得到49,38,65,76,13,27,97。
第二轮：比较并交换，次大元素76到倒数第二位，得到38,49,13,27,65,76,97。
重复直到有序。

快速排序

基本思想：选择一个基准元素，将序列分为小于基准和大于基准的两部分，递归排序这两部分。 算法步骤：

选择基准元素（通常为第一个元素）。
将序列分为左（小于基准）和右（大于基准）两部分。
对左右两部分递归执行快速排序。

示意：初始序列49,38,65,97,76,13,27，以49为基准：

分区后得到27,38,13，49，65,97,76。
递归对左半部分和右半部分排序，最终得到有序序列。

四、选择类排序

简单选择排序

基本思想：每次从未排序部分选择最小的元素，放到已排序序列的末尾。

算法步骤：

在序列中找到最小元素，与第一个元素交换。
在剩下的元素中找到最小元素，与第二个元素交换。
重复直到所有元素排序完成。

示意：初始序列49,38,65,97,76,13,27：

第一次选择13放到第一个位置，得到13,38,65,97,76,49,27。
第二次选择27放到第二个位置，得到13,27,65,97,76,49,38。
重复直到有序。

树形选择排序

基本思想：构造一棵完全二叉树，每次输出最小元素。

算法步骤：

构造完全二叉树。
每次输出根节点（最小元素）。
调整二叉树，重复直到所有元素输出。

堆排序

基本思想：利用堆（通常为大顶堆或小顶堆）的性质进行排序。

算法步骤：

构建初始堆。
输出堆顶元素，并将堆末尾元素移到堆顶。
调整堆，重复直到堆为空。

示意：初始序列49,38,65,97,76,13,27构建小顶堆：

第一次输出堆顶13，调整后得到新堆。
第二次输出堆顶27，调整后得到新堆。
重复直到所有元素输出，得到有序序列。

五、归并排序

基本思想：将序列分成若干子序列，分别排序后合并。

算法步骤：

将序列分成两部分。
对左右两部分分别递归归并排序。
合并两个已排序的子序列。

示意：初始序列49,38,65,97,76,13,27,25：

分解为49,38,65,97和76,13,27,25。
递归分解直到子序列长度为1。
合并子序列，最终得到有序序列。

六、分配类排序

多关键字排序

基本思想：按不同关键字依次排序，通常用于多字段数据。

算法步骤：

按最低位关键字排序。
按次低位关键字排序。
重复直到最高位关键字排序完成。

链式基数排序

基本思想：按数字的每一位分桶排序，通常使用链表实现。

算法步骤：

初始化10个桶（对应数字0-9）。
将数字按个位、十位等依次分入桶中。
收集桶中的数字，重复直到最高位处理完成。

基数排序的顺序表实现

基本思想：使用数组模拟桶，按位排序。

算法步骤：

初始化计数数组。
按位统计数字出现次数。
按位确定数字位置，重建序列。

七、代码实现

直接插入排序

C语言实现

#include <stdio.h>void InsertSort(int arr[], int n) {for (int i = 1; i < n; i++) { // 从第二个元素开始插入int temp = arr[i];int j = i - 1;// 将大于temp的元素后移while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp; // 插入到正确位置}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);InsertSort(arr, n);printf("排序后的数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

C++实现


#include <iostream>
using namespace std;void InsertSort(int arr[], int n) {for (int i = 1; i < n; i++) { // 从第二个元素开始插入int temp = arr[i];int j = i - 1;// 将大于temp的元素后移while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp; // 插入到正确位置}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);InsertSort(arr, n);cout << "排序后的数组：";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

Java实现


public class InsertSort {public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) { // 从第二个元素开始插入int temp = arr[i];int j = i - 1;// 将大于temp的元素后移while (j >= 0 && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp; // 插入到正确位置}}public static void main(String[] args) {int[] arr = {49, 38, 65, 97, 76, 13, 27};insertSort(arr);System.out.print("排序后的数组：");for (int num : arr) {System.out.print(num + " ");}}
}

Python实现


def insert_sort(arr):for i in range(1, len(arr)):  # 从第二个元素开始插入temp = arr[i]j = i - 1# 将大于temp的元素后移while j >= 0 and arr[j] > temp:arr[j + 1] = arr[j]j -= 1arr[j + 1] = temp  # 插入到正确位置if __name__ == "__main__":arr = [49, 38, 65, 97, 76, 13, 27]insert_sort(arr)print("排序后的数组：", arr)

快速排序

C语言实现

#include <stdio.h>void QuickSort(int arr[], int low, int high) {if (low < high) {int pivot = arr[low]; // 选择基准元素int i = low, j = high;// 分区操作while (i < j) {while (i < j && arr[j] >= pivot) { // 从右向左找小于pivot的元素j--;}arr[i] = arr[j]; // 将找到的元素放到左边while (i < j && arr[i] <= pivot) { // 从左向右找大于pivot的元素i++;}arr[j] = arr[i]; // 将找到的元素放到右边}arr[i] = pivot; // 基准元素归位QuickSort(arr, low, i - 1); // 递归排序左子数组QuickSort(arr, i + 1, high); // 递归排序右子数组}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);QuickSort(arr, 0, n - 1);printf("排序后的数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

C++实现


#include <iostream>
using namespace std;void QuickSort(int arr[], int low, int high) {if (low < high) {int pivot = arr[low]; // 选择基准元素int i = low, j = high;// 分区操作while (i < j) {while (i < j && arr[j] >= pivot) { // 从右向左找小于pivot的元素j--;}arr[i] = arr[j]; // 将找到的元素放到左边while (i < j && arr[i] <= pivot) { // 从左向右找大于pivot的元素i++;}arr[j] = arr[i]; // 将找到的元素放到右边}arr[i] = pivot; // 基准元素归位QuickSort(arr, low, i - 1); // 递归排序左子数组QuickSort(arr, i + 1, high); // 递归排序右子数组}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);QuickSort(arr, 0, n - 1);cout << "排序后的数组：";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

Java实现


public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = arr[low]; // 选择基准元素int i = low, j = high;// 分区操作while (i < j) {while (i < j && arr[j] >= pivot) { // 从右向左找小于pivot的元素j--;}arr[i] = arr[j]; // 将找到的元素放到左边while (i < j && arr[i] <= pivot) { // 从左向右找大于pivot的元素i++;}arr[j] = arr[i]; // 将找到的元素放到右边}arr[i] = pivot; // 基准元素归位quickSort(arr, low, i - 1); // 递归排序左子数组quickSort(arr, i + 1, high); // 递归排序右子数组}}public static void main(String[] args) {int[] arr = {49, 38, 65, 97, 76, 13, 27};quickSort(arr, 0, arr.length - 1);System.out.print("排序后的数组：");for (int num : arr) {System.out.print(num + " ");}}
}

Python实现


def quick_sort(arr, low, high):if low < high:pivot = arr[low]  # 选择基准元素i = lowj = high# 分区操作while i < j:while i < j and arr[j] >= pivot:  # 从右向左找小于pivot的元素j -= 1arr[i] = arr[j]  # 将找到的元素放到左边while i < j and arr[i] <= pivot:  # 从左向右找大于pivot的元素i += 1arr[j] = arr[i]  # 将找到的元素放到右边arr[i] = pivot  # 基准元素归位quick_sort(arr, low, i - 1)  # 递归排序左子数组quick_sort(arr, i + 1, high)  # 递归排序右子数组if __name__ == "__main__":arr = [49, 38, 65, 97, 76, 13, 27]quick_sort(arr, 0, len(arr) - 1)print("排序后的数组：", arr)

堆排序

C语言实现


#include <stdio.h>void HeapSort(int arr[], int n) {// 构建初始大顶堆for (int i = n / 2 - 1; i >= 0; i--) {int k = i;int temp = arr[k];int flag = 1;while (flag) {flag = 0;if (2 * k + 1 < n && arr[2 * k + 1] > temp) {int largerChild = 2 * k + 1;if (2 * k + 2 < n && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}arr[k] = arr[largerChild];k = largerChild;flag = 1;}}arr[k] = temp;}// 将堆顶元素与末尾元素交换，并重新调整堆for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;int k = 0;int flag = 1;while (flag) {flag = 0;if (2 * k + 1 < i && arr[2 * k + 1] > arr[k]) {int largerChild = 2 * k + 1;if (2 * k + 2 < i && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}int t = arr[k];arr[k] = arr[largerChild];arr[largerChild] = t;k = largerChild;flag = 1;}}}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);printf("排序后的数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

C++实现


#include <iostream>
using namespace std;void HeapSort(int arr[], int n) {// 构建初始大顶堆for (int i = n / 2 - 1; i >= 0; i--) {int k = i;int temp = arr[k];int flag = 1;while (flag) {flag = 0;if (2 * k + 1 < n && arr[2 * k + 1] > temp) {int largerChild = 2 * k + 1;if (2 * k + 2 < n && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}arr[k] = arr[largerChild];k = largerChild;flag = 1;}}arr[k] = temp;}// 将堆顶元素与末尾元素交换，并重新调整堆for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;int k = 0;int flag = 1;while (flag) {flag = 0;if (2 * k + 1 < i && arr[2 * k + 1] > arr[k]) {int largerChild = 2 * k + 1;if (2 * k + 2 < i && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}int t = arr[k];arr[k] = arr[largerChild];arr[largerChild] = t;k = largerChild;flag = 1;}}}
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27};int n = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);cout << "排序后的数组：";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

Java实现


public class HeapSort {public static void heapSort(int[] arr) {int n = arr.length;// 构建初始大顶堆for (int i = n / 2 - 1; i >= 0; i--) {int k = i;int temp = arr[k];int flag = 1;while (flag != 0) {flag = 0;if (2 * k + 1 < n && arr[2 * k + 1] > temp) {int largerChild = 2 * k + 1;if (2 * k + 2 < n && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}arr[k] = arr[largerChild];k = largerChild;flag = 1;}}arr[k] = temp;}// 将堆顶元素与末尾元素交换，并重新调整堆for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;int k = 0;int flag = 1;while (flag != 0) {flag = 0;if (2 * k + 1 < i && arr[2 * k + 1] > arr[k]) {int largerChild = 2 * k + 1;if (2 * k + 2 < i && arr[2 * k + 2] > arr[largerChild]) {largerChild = 2 * k + 2;}int t = arr[k];arr[k] = arr[largerChild];arr[largerChild] = t;k = largerChild;flag = 1;}}}}public static void main(String[] args) {int[] arr = {49, 38, 65, 97, 76, 13, 27};heapSort(arr);System.out.print("排序后的数组：");for (int num : arr) {System.out.print(num + " ");}}
}

Python实现


def heap_sort(arr):n = len(arr)# 构建初始大顶堆for i in range(n // 2 - 1, -1, -1):k = itemp = arr[k]flag = 1while flag:flag = 0if 2 * k + 1 < n and arr[2 * k + 1] > temp:larger_child = 2 * k + 1if 2 * k + 2 < n and arr[2 * k + 2] > arr[larger_child]:larger_child = 2 * k + 2arr[k] = arr[larger_child]k = larger_childflag = 1arr[k] = temp# 将堆顶元素与末尾元素交换，并重新调整堆for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]k = 0flag = 1while flag:flag = 0if 2 * k + 1 < i and arr[2 * k + 1] > arr[k]:larger_child = 2 * k + 1if 2 * k + 2 < i and arr[2 * k + 2] > arr[larger_child]:larger_child = 2 * k + 2arr[k], arr[larger_child] = arr[larger_child], arr[k]k = larger_childflag = 1if __name__ == "__main__":arr = [49, 38, 65, 97, 76, 13, 27]heap_sort(arr)print("排序后的数组：", arr)

基数排序

C语言实现

#include <stdio.h>
#include <stdlib.h>void RadixSort(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) { // 找到最大值if (arr[i] > max) {max = arr[i];}}int digits = 0;while (max > 0) { // 计算最大值的位数digits++;max /= 10;}int* temp = (int*)malloc(n * sizeof(int)); // 临时数组int* count = (int*)malloc(10 * sizeof(int)); // 计数数组for (int d = 0; d < digits; d++) { // 按每一位排序int divisor = (int)pow(10, d);for (int i = 0; i < 10; i++) { // 初始化计数数组count[i] = 0;}for (int i = 0; i < n; i++) { // 计数int digit = (arr[i] / divisor) % 10;count[digit]++;}for (int i = 1; i < 10; i++) { // 累加计数count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) { // 放置元素int digit = (arr[i] / divisor) % 10;temp[count[digit] - 1] = arr[i];count[digit]--;}for (int i = 0; i < n; i++) { // 拷贝回原数组arr[i] = temp[i];}}free(temp);free(count);
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27, 25};int n = sizeof(arr) / sizeof(arr[0]);RadixSort(arr, n);printf("排序后的数组：");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

C++实现


#include <iostream>
#include <cmath>
using namespace std;void RadixSort(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) { // 找到最大值if (arr[i] > max) {max = arr[i];}}int digits = 0;while (max > 0) { // 计算最大值的位数digits++;max /= 10;}int* temp = new int[n]; // 临时数组int* count = new int[10]; // 计数数组for (int d = 0; d < digits; d++) { // 按每一位排序int divisor = pow(10, d);for (int i = 0; i < 10; i++) { // 初始化计数数组count[i] = 0;}for (int i = 0; i < n; i++) { // 计数int digit = (arr[i] / divisor) % 10;count[digit]++;}for (int i = 1; i < 10; i++) { // 累加计数count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) { // 放置元素int digit = (arr[i] / divisor) % 10;temp[count[digit] - 1] = arr[i];count[digit]--;}for (int i = 0; i < n; i++) { // 拷贝回原数组arr[i] = temp[i];}}delete[] temp;delete[] count;
}int main() {int arr[] = {49, 38, 65, 97, 76, 13, 27, 25};int n = sizeof(arr) / sizeof(arr[0]);RadixSort(arr, n);cout << "排序后的数组：";for (int i = 0; i < n; i++) {cout << arr[i] << " ";}return 0;
}

Java实现


import java.util.Arrays;public class RadixSort {public static void radixSort(int[] arr) {int max = arr[0];for (int i = 1; i < arr.length; i++) { // 找到最大值if (arr[i] > max) {max = arr[i];}}int digits = 0;while (max > 0) { // 计算最大值的位数digits++;max /= 10;}int[] temp = new int[arr.length]; // 临时数组for (int d = 0; d < digits; d++) { // 按每一位排序int divisor = (int) Math.pow(10, d);int[] count = new int[10]; // 计数数组for (int i = 0; i < arr.length; i++) { // 计数int digit = (arr[i] / divisor) % 10;count[digit]++;}for (int i = 1; i < 10; i++) { // 累加计数count[i] += count[i - 1];}for (int i = arr.length - 1; i >= 0; i--) { // 放置元素int digit = (arr[i] / divisor) % 10;temp[count[digit] - 1] = arr[i];count[digit]--;}for (int i = 0; i < arr.length; i++) { // 拷贝回原数组arr[i] = temp[i];}}}public static void main(String[] args) {int[] arr = {49, 38, 65, 97, 76, 13, 27, 25};radixSort(arr);System.out.print("排序后的数组：");System.out.println(Arrays.toString(arr));}
}

Python实现


def radix_sort(arr):max_num = max(arr)digits = 0while max_num > 0:digits += 1max_num //= 10temp = [0] * len(arr)for d in range(digits):divisor = 10 ** dcount = [0] * 10for num in arr:digit = (num // divisor) % 10count[digit] += 1for i in range(1, 10):count[i] += count[i - 1]for i in range(len(arr)-1, -1, -1):digit = (arr[i] // divisor) % 10temp[count[digit]-1] = arr[i]count[digit] -= 1for i in range(len(arr)):arr[i] = temp[i]if __name__ == "__main__":arr = [49, 38, 65, 97, 76, 13, 27, 25]radix_sort(arr)print("排序后的数组：", arr)

八、总结与提高

各种排序方法的综合比较

排序方法	时间性能分析	空间性能分析	应用场景
直接插入排序	O(n²)	O(1)	小规模数据或基本有序的数据
折半插入排序	O(n²)	O(1)	小规模数据或基本有序的数据
希尔排序	O(n1.3)	O(1)	中等规模数据
冒泡排序	O(n²)	O(1)	小规模数据或基本有序的数据
快速排序	O(nlogn)	O(logn)	大规模数据，要求平均性能好
简单选择排序	O(n²)	O(1)	小规模数据
树形选择排序	O(nlogn)	O(n)	要求稳定的排序
堆排序	O(nlogn)	O(1)	大规模数据，要求最坏情况下性能好
归并排序	O(nlogn)	O(n)	要求稳定的排序且对大规模数据性能好
基数排序	O(dn)	O(n)	数据范围有限且要求稳定的排序