
排序是将一组元素按照某种规律排列成一个序列的过程。排序主要分为内部排序(数据在内存中完成排序)和外部排序(数据量过大,需借助外部存储完成排序)。常用排序算法有插入类、交换类、选择类、归并类和分配类等。
基本思想:将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
算法步骤:
示意: 假设初始序列为49,38,65,97,76,13,27。排序过程如下:
基本思想:在直接插入排序的基础上,使用折半查找法确定插入位置。
算法步骤:
基本思想:将整个序列分成多个子序列分别进行直接插入排序,子序列的初始步长较大,逐渐减小到1。
算法步骤:
示意图: 初始序列13,14,94,33,82,25,59,94,65,23,45,27,73,25,增量取5:
基本思想:通过比较相邻元素,将较大的元素逐步“冒泡”到序列末尾。
算法步骤:
示意: 初始序列49,38,65,97,76,13,27:
基本思想:选择一个基准元素,将序列分为小于基准和大于基准的两部分,递归排序这两部分。 算法步骤:
示意: 初始序列49,38,65,97,76,13,27,以49为基准:
基本思想:每次从未排序部分选择最小的元素,放到已排序序列的末尾。
算法步骤:
示意: 初始序列49,38,65,97,76,13,27:
基本思想:构造一棵完全二叉树,每次输出最小元素。
算法步骤:
基本思想:利用堆(通常为大顶堆或小顶堆)的性质进行排序。
算法步骤:
示意: 初始序列49,38,65,97,76,13,27构建小顶堆:
基本思想:将序列分成若干子序列,分别排序后合并。
算法步骤:
示意: 初始序列49,38,65,97,76,13,27,25:
基本思想:按不同关键字依次排序,通常用于多字段数据。
算法步骤:
基本思想:按数字的每一位分桶排序,通常使用链表实现。
算法步骤:
基本思想:使用数组模拟桶,按位排序。
算法步骤:
#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;
}
#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;
}
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 + " ");
}
}
}
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 -= 1
arr[j + 1] = temp # 插入到正确位置
if __name__ == "__main__":
arr = [49, 38, 65, 97, 76, 13, 27]
insert_sort(arr)
print("排序后的数组:", arr)
#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;
}
#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;
}
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 + " ");
}
}
}
def quick_sort(arr, low, high):
if low < high:
pivot = arr[low] # 选择基准元素
i = low
j = high
# 分区操作
while i < j:
while i < j and arr[j] >= pivot: # 从右向左找小于pivot的元素
j -= 1
arr[i] = arr[j] # 将找到的元素放到左边
while i < j and arr[i] <= pivot: # 从左向右找大于pivot的元素
i += 1
arr[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)
#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;
}
#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;
}
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 + " ");
}
}
}
def heap_sort(arr):
n = len(arr)
# 构建初始大顶堆
for i in range(n // 2 - 1, -1, -1):
k = i
temp = arr[k]
flag = 1
while flag:
flag = 0
if 2 * k + 1 < n and arr[2 * k + 1] > temp:
larger_child = 2 * k + 1
if 2 * k + 2 < n and arr[2 * k + 2] > arr[larger_child]:
larger_child = 2 * k + 2
arr[k] = arr[larger_child]
k = larger_child
flag = 1
arr[k] = temp
# 将堆顶元素与末尾元素交换,并重新调整堆
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
k = 0
flag = 1
while flag:
flag = 0
if 2 * k + 1 < i and arr[2 * k + 1] > arr[k]:
larger_child = 2 * k + 1
if 2 * k + 2 < i and arr[2 * k + 2] > arr[larger_child]:
larger_child = 2 * k + 2
arr[k], arr[larger_child] = arr[larger_child], arr[k]
k = larger_child
flag = 1
if __name__ == "__main__":
arr = [49, 38, 65, 97, 76, 13, 27]
heap_sort(arr)
print("排序后的数组:", arr)
#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;
}
#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;
}
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));
}
}
def radix_sort(arr):
max_num = max(arr)
digits = 0
while max_num > 0:
digits += 1
max_num //= 10
temp = [0] * len(arr)
for d in range(digits):
divisor = 10 ** d
count = [0] * 10
for num in arr:
digit = (num // divisor) % 10
count[digit] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(len(arr)-1, -1, -1):
digit = (arr[i] // divisor) % 10
temp[count[digit]-1] = arr[i]
count[digit] -= 1
for 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) | 数据范围有限且要求稳定的排序 |
通过学习各种排序算法的基本原理、实现方法和性能分析,可以帮助我们更好地理解和应用排序算法。在实际编程中,可以根据具体需求选择合适的排序算法来提高程序的效率。