算法学习：一维数组的排序算法

【排序算法】八种排序算法可视化过程_哔哩哔哩_bilibili

1，冒泡排序：

冒泡排序(Bubble Sort):

冒泡排序是一种简单的排序算法,它通过重复地交换相邻的元素,直到整个序列有序。
算法思路是:从第一个元素开始,依次比较相邻的两个元素,如果前者大于后者,就交换它们的位置。这样一轮下来,最大的元素就会"冒泡"到数组的末尾。
重复这个过程,直到整个数组有序。

C语言实现：

void bubble_sort(int arr[], int n) {// 冒泡排序实现for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

python实现：

def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

2，选择排序：

选择排序(Selection Sort):

选择排序是一种简单直观的排序算法。
算法思路是:首先在未排序序列中找到最小（大）元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小（大）元素,放到已排序序列的末尾。
重复这个过程,直到整个数组有序。

C语言实现：

void selection_sort(int arr[], int n) {// 选择排序实现for (int i = 0; i < n - 1; i++) {int min_idx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 交换 arr[i] 和 arr[min_idx]int temp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = temp;}
}

python实现：

def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr

3，插入排序：

插入排序(Insertion Sort):

插入排序是一种简单直观的排序算法。
算法思路是:将数组中的元素逐个插入到已排序的子数组中,直到整个数组有序。
具体过程是:从第二个元素开始,将当前元素与已排序的子数组进行比较和插入。

C语言实现：

void insertion_sort(int arr[], int n) {// 插入排序实现for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

python实现：

def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr

4，堆排序：

堆排序(Heap Sort):

堆排序利用二叉堆的特性进行排序。
算法思路是:首先将待排序数组构建成一个最大堆,然后将堆顶元素(即最大值)与堆末尾元素交换,然后对剩余元素重新调整为最大堆,重复这个过程直到整个数组有序。

C语言实现：

void heapify(int arr[], int n, int i) {//    // 堆排序实现int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {// 交换 arr[i] 和 arr[largest]int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}void heap_sort(int arr[], int n) {// 堆排序实现// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 从堆中提取元素for (int i = n - 1; i > 0; i--) {// 交换 arr[0] 和 arr[i]int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}

python实现：

def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[largest] < arr[left]:largest = leftif right < n and arr[largest] < arr[right]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)# 构建大顶堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐步将堆顶元素与末尾元素交换并重新调整堆for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr

5，快速排序：

它的基本思想是:

从数列中挑出一个元素,称为 "基准"（pivot）。
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

C语言实现：

//快速排序
// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 分区操作
int partition(int arr[], int low, int high) {int pivot = arr[high];  // 将最后一个元素选为基准int i = (low - 1);      // 较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于 pivotif (arr[j] <= pivot) {i++;            // 将较小元素的索引递增swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);// 递归地对分区进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}

python实现：

def partition(arr, low, high):i = (low-1)pivot = arr[high]for j in range(low, high):if arr[j] < pivot:i = i+1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return (i+1)

6，并归排序：

归并排序是一种采用分治策略的高效排序算法。
算法思路是:将待排序数组递归地分成两半,直到每个子数组只有一个元素,然后将这些子数组合并,得到最终有序的数组。
具体过程是:将数组一分为二,递归地对两个子数组进行排序,然后将两个有序的子数组合并成一个有序数组。

C语言实现：

// 并归排序
void merge(int arr[], int left[], int left_size, int right[], int right_size) {int i = 0, j = 0, k = 0;// 合并 left 和 right 数组while (i < left_size && j < right_size) {if (left[i] < right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 将剩余元素添加到 arr 中while (i < left_size) {arr[k++] = left[i++];}while (j < right_size) {arr[k++] = right[j++];}
}void merge_sort(int arr[], int size) {if (size <= 1) {return;}int mid = size / 2;int *left = (int *)malloc(mid * sizeof(int));int *right = (int *)malloc((size - mid) * sizeof(int));// 递归地对左右子数组进行排序for (int i = 0; i < mid; i++) {left[i] = arr[i];}merge_sort(left, mid);for (int i = mid; i < size; i++) {right[i - mid] = arr[i];}merge_sort(right, size - mid);// 合并左右子数组merge(arr, left, mid, right, size - mid);// 释放动态分配的内存free(left);free(right);
}

python实现：

def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

7，举例子

来随机生成一个长度为100,000的一维数组，并使用上述算法进行排序。

（由于数据量太大，电脑可能由于内存问题，一块运行会导致C语言代码崩溃，建议便注释边运行，python不会出现种情况。非计算机专业学生，说法错误欢迎指正）

C语言版代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>#define SIZE 100000void bubble_sort(int arr[], int n) {// 冒泡排序实现for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void selection_sort(int arr[], int n) {// 选择排序实现for (int i = 0; i < n - 1; i++) {int min_idx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 交换 arr[i] 和 arr[min_idx]int temp = arr[i];arr[i] = arr[min_idx];arr[min_idx] = temp;}
}void insertion_sort(int arr[], int n) {// 插入排序实现for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}void heapify(int arr[], int n, int i) {//    // 堆排序实现int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {// 交换 arr[i] 和 arr[largest]int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}void heap_sort(int arr[], int n) {// 堆排序实现// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 从堆中提取元素for (int i = n - 1; i > 0; i--) {// 交换 arr[0] 和 arr[i]int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}// 并归排序
void merge(int arr[], int left[], int left_size, int right[], int right_size) {int i = 0, j = 0, k = 0;// 合并 left 和 right 数组while (i < left_size && j < right_size) {if (left[i] < right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 将剩余元素添加到 arr 中while (i < left_size) {arr[k++] = left[i++];}while (j < right_size) {arr[k++] = right[j++];}
}void merge_sort(int arr[], int size) {if (size <= 1) {return;}int mid = size / 2;int *left = (int *)malloc(mid * sizeof(int));int *right = (int *)malloc((size - mid) * sizeof(int));// 递归地对左右子数组进行排序for (int i = 0; i < mid; i++) {left[i] = arr[i];}merge_sort(left, mid);for (int i = mid; i < size; i++) {right[i - mid] = arr[i];}merge_sort(right, size - mid);// 合并左右子数组merge(arr, left, mid, right, size - mid);// 释放动态分配的内存free(left);free(right);
}//快速排序
// 交换两个元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 分区操作
int partition(int arr[], int low, int high) {int pivot = arr[high];  // 将最后一个元素选为基准int i = (low - 1);      // 较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于 pivotif (arr[j] <= pivot) {i++;            // 将较小元素的索引递增swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}// 快速排序函数
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);// 递归地对分区进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}int main() {int arr[SIZE];// 生成随机数组srand(time(NULL));for (int i = 0; i < SIZE; i++) {arr[i] = rand() % 1000000;}// 冒泡排序 // Bubble sort time: 21.614000 secondsint bubble_arr[SIZE];memcpy(bubble_arr, arr, sizeof(arr));clock_t bubble_start = clock();bubble_sort(bubble_arr, SIZE);clock_t bubble_end = clock();printf("Bubble sort time: %f seconds\n", (double)(bubble_end - bubble_start) / CLOCKS_PER_SEC);//// // 选择排序 //Selection sort time: 4.120000 seconds// int select_arr[SIZE];// memcpy(select_arr, arr, sizeof(arr));// clock_t select_start = clock();// selection_sort(select_arr, SIZE);// clock_t select_end = clock();// printf("Selection sort time: %f seconds\n", (double)(select_end - select_start) / CLOCKS_PER_SEC);//// // 插入排序 //Insertion sort time: 2.663000 seconds// int insert_arr[SIZE];// memcpy(insert_arr, arr, sizeof(arr));// clock_t insert_start = clock();// insertion_sort(insert_arr, SIZE);// clock_t insert_end = clock();// printf("Insertion sort time: %f seconds\n", (double)(insert_end - insert_start) / CLOCKS_PER_SEC);//// // 堆排序 //Heap sort time: 0.015000 seconds// int heap_arr[SIZE];// memcpy(heap_arr, arr, sizeof(arr));// clock_t heap_start = clock();// heap_sort(heap_arr, SIZE);// clock_t heap_end = clock();// printf("Heap sort time: %f seconds\n", (double)(heap_end - heap_start) / CLOCKS_PER_SEC);//// // 归并排序 //Merge sort time: 0.035000 seconds// int merge_arr[SIZE];// memcpy(merge_arr, arr, sizeof(arr));// clock_t merge_start = clock();// merge_sort(merge_arr, SIZE);// clock_t merge_end = clock();// printf("Merge sort time: %f seconds\n", (double)(merge_end - merge_start) / CLOCKS_PER_SEC);// //快速排序 //Quick sort time: 0.010000 seconds// int quickSort_arr[SIZE];// memcpy(quickSort_arr, arr, sizeof(arr));// clock_t quick_start = clock();// int n = sizeof(quickSort_arr) / sizeof(quickSort_arr[0]);// quickSort(quickSort_arr, 0, n-1);// clock_t quick_end = clock();// printf("Quick sort time: %f seconds\n", (double)(quick_end - quick_start) / CLOCKS_PER_SEC);return 0;
}

python版代码：

import random
import time# 冒泡排序: Bubble sort time: 663.5839667320251 seconds
def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr# 选择排序: Selection sort time: 285.8419885635376 seconds
def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr# 插入排序:
def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr# 归并排序: Merge sort time: 0.539679765701294 seconds
def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr# 快速排序: Quick sort time: 0.31060314178466797 seconds
def partition(arr, low, high):i = (low-1)pivot = arr[high]for j in range(low, high):if arr[j] < pivot:i = i+1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return (i+1)def quick_sort(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)quick_sort(arr, pi+1, high)return arr# 堆排序
def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[largest] < arr[left]:largest = leftif right < n and arr[largest] < arr[right]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)# 构建大顶堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐步将堆顶元素与末尾元素交换并重新调整堆for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr# 生成随机数组
data = [random.randint(0, 1000000) for _ in range(100000)]# 冒泡排序 Bubble sort time: 663.5839667320251 seconds
start_time = time.time()
bubble_sorted = bubble_sort(data.copy())
bubble_time = time.time() - start_time
print("Bubble sort time:", bubble_time, "seconds")
#
# 选择排序 Selection sort time: 285.8419885635376 seconds
start_time = time.time()
selection_sorted = selection_sort(data.copy())
selection_time = time.time() - start_time
print("Selection sort time:", selection_time, "seconds")
#
# 插入排序 Insertion sort time: 396.2825345993042 seconds
start_time = time.time()
insertion_sorted = insertion_sort(data.copy())
insertion_time = time.time() - start_time
print("Insertion sort time:", insertion_time, "seconds")
#
# 归并排序 Merge sort time: 0.539679765701294 seconds
start_time = time.time()
merge_sorted = merge_sort(data.copy())
merge_time = time.time() - start_time
print("Merge sort time:", merge_time, "seconds")
#
# 快速排序 Quick sort time: 0.31060314178466797 seconds
start_time = time.time()
quick_sorted = quick_sort(data.copy(), 0, len(data) - 1)
quick_time = time.time() - start_time
print("Quick sort time:", quick_time, "seconds")# 堆排序 heap_sorted time: heap_sorted time: 0.8571550846099854 seconds
start_time = time.time()
heap_sorted = heap_sort(data.copy())
heap_sorted_time = time.time() - start_time
print("heap_sorted time:", heap_sorted_time, "seconds")

结果对比：

不仅是算法上，C与python的执行效率上都有区别（实验存在偶然性，本文提供代码可以自己验证）

绘图代码：

import matplotlib.pyplot as pltalgorithms_c = ['Bubble Sort','Selection Sort','Insertion Sort','Merge Sort','Quick Sort','Heap Sort']
times_c = ['21.614000','4.120000','2.663000','0.035000','0.010000','0.015000']algorithms_python = ['Bubble Sort','Selection Sort','Insertion Sort','Merge Sort','Quick Sort','Heap Sort']
times_python = ['663.583','285.841','396.282','0.539','0.310','0.857']plt.figure(figsize=(25, 12))
plt.subplot(1, 2, 1)
plt.bar(algorithms_c, times_c)
plt.xlabel('Sorting Algorithms')
plt.ylabel('Time (seconds)')
plt.title('Comparison of Sorting Algorithms')
plt.xticks(rotation=45)
plt.title('Inference Time of Sorting Algorithms in C')plt.subplot(1,2,2)
plt.bar(algorithms_c, times_c,color='red')
plt.xlabel('Sorting Algorithms')
plt.ylabel('Time (seconds)')
plt.title('Comparison of Sorting Algorithms')
plt.xticks(rotation=45)
plt.title('Inference Time of Sorting Algorithms in Python')
plt.show()