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

2024-08-28 01:52

本文主要是介绍算法学习:一维数组的排序算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【排序算法】八种排序算法可视化过程_哔哩哔哩_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,快速排序:

它的基本思想是:

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

 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()

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

这篇关于算法学习:一维数组的排序算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113401

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1