基本排序算法代码实现,以及使用场景推荐
2021/5/30 12:22:57
本文主要是介绍基本排序算法代码实现,以及使用场景推荐,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 冒泡排序
平均复杂度为 O(n^2), 稳定
1 // 冒泡排序 2 public static void Bubble_Sort(int[] A, int n){ 3 int flag = 0; 4 // 进行 n - 1 轮冒泡 5 for(int i = n - 1; i > 0; i--){ 6 flag = 0; 7 for(int j = 0; j < i; j++){ 8 if(A[j] > A[j + 1]){ 9 // 交换 A[j] 和 A[j + 1] 10 A[j] ^= A[j + 1]; 11 A[j + 1] ^= A[j]; 12 A[j] ^= A[j + 1]; 13 flag = 1; 14 } 15 } 16 if(flag == 0) // 此轮没发生交换,排序结束 17 break; 18 } 19 }
2. 插入排序
最好情况是 序列本身有序,此时复杂度为 O(n), 但是平均复杂度为 O(n^2), 稳定,适合 序列中的元素相对有序的场景
1 // 插入排序 2 public static void Insertion_Sort(int[] A, int n){ 3 int temp, i, j; 4 for(i = 1; i < n; i++){ 5 temp = A[i]; 6 for(j = i; j > 0 && A[j - 1] > temp; j--){ 7 A[j] = A[j - 1]; 8 } 9 A[j] = temp; 10 } 11 }
3. 希尔排序
平均复杂度 为 O(n^d), 不稳定
1 // 希尔排序, 最坏情况 为 O(n^2) 2 static void Shell_Sort(int A[], int n){ 3 int d,i, j, temp; // d 为增量 4 for(d = n / 2; d > 0; d /= 2){ 5 // 内部是一个增量为 d 的插入排序 6 for(i = d; i < n; i++){ 7 temp = A[i]; 8 for(j = i; j >= d && A[j - d] > temp; j -= d) 9 A[j] = A[j - d]; 10 A[j] = temp; 11 } 12 } 13 }
4. 堆排序
平均复杂度为 O(nlogn) , 不稳定
1 // 堆排序 2 public static void downAdjust(int[] A, int p, int n){ 3 int parent, child = p; 4 int x = A[p]; // 取出根节点的值 5 for(parent = p; (2 * parent + 1) < n; parent = child){ 6 child = 2 * parent + 1; 7 // 如果右孩子存在且比左孩子大 8 if(child + 1 < n && A[child + 1] > A[child]){ 9 child++; 10 } 11 if(x >= A[child]) // 与最大孩子结点比较, 如果父节点大,说明找到了位置 12 break; 13 else 14 A[parent] = A[child]; // 否则让最大孩子上位 15 } 16 A[parent] = x; // 退出循环说明找到了 p 的位置 17 } 18 19 public static void Heap_Sort(int[] A, int n){ 20 // 建立最大堆 21 for(int i = n / 2 - 1; i >= 0; i--){ // 从第一个右孩子的结点向下调整 22 downAdjust(A, i, n); 23 } 24 for(int i = n - 1; i > 0; i--){ 25 // 将堆顶元素与当前未排序的最后一个元素交换 26 int temp = A[i]; 27 A[i] = A[0]; 28 A[0] = temp; 29 downAdjust(arr, 0, i); 30 } 31 }
5. 选择排序
平均复杂度 O(n^2), 不稳定,如序列:2 2 3 4 5 1
1 // 选择排序, 最坏情况为 O(n^2), 不稳定 如 2 2 3 4 5 1 2 public static void Selection_Sort(int[] A, int n){ 3 int k, temp; 4 for(int i = 0; i < n - 1; i++){ 5 k = i; 6 for(int j = i + 1; j < n; j++){ 7 if(A[j] < A[k]) 8 k = j; // 找到最小的元素的下标 9 } 10 temp = A[k]; 11 A[k] = A[i]; 12 A[i] = temp; 13 } 14 }
6. 归并排序
平均复杂度为 O(nlogn), 额外空间复杂度为 O(n), 稳定
1 public static void Merge(int[] A, int[] temp, int LL, int LR, int RL, int RR){ 2 int left = LL; 3 int index = LL; 4 while(LL <= LR && RL <= RR) { 5 if (A[LL] <= A[RL]) { 6 temp[index++] = A[LL++]; 7 } else { 8 temp[index++] = A[RL++]; 9 } 10 } 11 while(LL <= LR) 12 temp[index++] = A[LL++]; 13 while(RL <= RR) 14 temp[index++] = A[RL++]; 15 16 // 将temp元素 复制到 A 数组中 17 for(int i = left; i < index; i++) 18 A[i] = temp[i]; 19 20 } 21 22 public static void Msort(int[] A, int temp[], int left, int right){ 23 int center; 24 if(left < right){ 25 center = (right + left) / 2; 26 Msort(A, temp, left, center); // 归并做半段元素 27 Msort(A, temp, center + 1, right); // 归并y右半段元素 28 Merge(A, temp, left, center, center + 1, right); // 合并左右两段 29 } 30 } 31 32 // 归并排序 递归方式 复杂度为 O(nlogn) 33 public static void MergeSort(int[] A, int n){ 34 int[] temp = new int[1000]; // 借助一个辅助富足,每次将两段区间排好序的元素存在temp数组总 35 Msort(A, temp, 0, n - 1); 36 }
7. 快速排序
平均复杂度为 O(nlogn), 不稳定
1 // 随机选取主元,对区间 [left, right] 进行划分 2 public static int randPartition(int[] A, int left, int right){ 3 // 生成一个 [left, right] 范围内的随机数, 随机让排序平均复杂度更低 4 Random r = new Random(); 5 int p = r.nextInt(right - left) + left; 6 7 int temp = A[left]; 8 A[left] = A[p]; 9 A[p] = temp; 10 11 int pivot = A[left]; 12 while(left < right){ // 只要 left 与 right 不相遇 13 while(left < right && A[right] > pivot) 14 right--; 15 A[left] = A[right]; 16 while(left < right && A[left] <= pivot) 17 left++; 18 A[right] = A[left]; 19 } 20 A[left] = pivot; 21 return left; 22 } 23 24 // 快速排序, left 与 right 初值为序列首尾下标 25 public static void quickSortHelp(int[] A, int left, int right){ 26 if(left < right){ // 当区间长度超过 1 时 27 // 将 [left, right] 按照 A[left] 为主元,一分为二 28 int pos = randPartition(A, left, right); 29 quickSortHelp(A, left, pos - 1); 30 quickSortHelp(A, pos + 1, right); 31 } 32 } 33 34 public static void quickSort(int[] A, int n){ 35 quickSortHelp(A, 0, n - 1); 36 }
算法比较:
不同场景的排序算法选择:
如果序列相对有序,则选择 插入排序;
如果 序列分布散乱随机,则用归并排序或者快速排序;
如果序列元素都限定在某个范围内,则用基数排序;
如果要求排序稳定,则选用归并排序或插入排序或基数排序
这篇关于基本排序算法代码实现,以及使用场景推荐的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求