成都高新区国土规划建设局网站,镇江市建设工程质量监督局网站,爱淘宝淘宝网首页,google谷歌本次介绍内容参考自#xff1a;十大经典排序算法#xff08;C实现#xff09; - fengMisaka - 博客园 (cnblogs.com) 排序算法是《数据结构与算法》中最基本的算法之一。 十种常见排序算法可以分为两大类#xff1a; 比较类排序#xff1a;通过比较来决定元素间的相对次序… 本次介绍内容参考自十大经典排序算法C实现 - fengMisaka - 博客园 (cnblogs.com) 排序算法是《数据结构与算法》中最基本的算法之一。 十种常见排序算法可以分为两大类 比较类排序通过比较来决定元素间的相对次序时间复杂度为 O(nlogn)O(n²)。非比较类排序不通过比较来决定元素间的相对次序其时间复杂度可以突破 O(nlogn)以线性时间运行。 【十大经典排序算法分类】 【十大经典排序算法的复杂度分析】 名词解释 时间/空间复杂度描述一个算法执行时间/占用空间与数据规模的增长关系。 n待排序列的个数。 k“桶”的个数上面的三种非比较类排序都是基于“桶”的思想实现的。 In-place原地算法指的是占用常量内存不占用额外内存。即空间复杂度为 O(1) 。 Out-place非原地算法占用额外内存。 稳定性假设待排序列中两元素相等排序前后这两个相等元素的相对位置不变则认为是稳定的。 一、归并排序Merge-Sort 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为 2- 路归并。
1.1、算法描述
把长度为 n 的输入序列分成两个长度为 n/2 的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。
1.2、动图演示 归并排序动图演示 1.3、C编码
/**
* version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* file MergeSort.hpp
* brief 归并排序
* autor 写代码的小恐龙er
* date 2024/03/05
*/// 【分治法】 【递归法】
// 时间复杂度O(n * log n)
// 空间复杂度O(n)/* 将 arr[l..m] 和 arr[m1..r] 归并 */
void Merge(int arr[], int l, int m, int r) {// 将arr数组分成左右两个 有序序列 再合并在一起int size r - l 1;vectorint newArr(size, 0);// k代表新数组的下标int i 0, j m 1, k 0;// 将分组后的两边按照递增顺序排列while(i m; j r) newArr[k] arr[i] arr[j] ? arr[i] : arr[j];while(i m) newArr[k] arr[i];while(j r) newArr[k] arr[j];// 重新赋值k 0;for(i l; i r; i){arr[i] newArr[k];}
}void MergeSort(int arr[], int l, int r) {// 终止条件if (l r) return;// 将 arr[l..r] 平分为 arr[l..m] 和 arr[m1..r]int m (l r) / 2;// 分别递归地将子序列排序为有序数列MergeSort(arr, l, m);MergeSort(arr, m 1, r);// 将两个排序后的子序列再归并到 arrMerge(arr, l, m, r);
} 1.4 、算法分析 归并排序在实现上通常采用 Out-place 排序即需用到 O(n) 的额外空间的排序在排序过程中属于稳定的排序算法其时间复杂度均为O(n * log n)。在算法实现上采用了分治法与递归思想。 二、快速排序Quick Sort 快速排序Quick Sort是冒泡排序的改进版之所以“快速”是因为使用了分治法。它也属于交换排序通过元素之间的位置交换来达到排序的目的。 基本思想通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序。
2.1 、算法描述
从数列中挑出一个元素称为 “基准”pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.2 、动图演示 快速排序动图演示 2.3、C编码
/**
* version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved
* file QuickSort.hpp
* brief 快速排序
* autor 写代码的小恐龙er
* date 2024/03/05
*/// 【分治法】 【递归法】
// 时间复杂度O(n * log n)
// 空间复杂度O(log n)void QuickSort(int *arr[], int begin, int end)
{ // 终止条件if (begin end) // 递归直到start end为止return;// 基准数int pivot arr[begin]; int i begin;int j end;while (i ! j){// 从右向左找比基准数小的数 要先从右边开始找while (arr[j] pivot i j) j--;// 从左向右找比基准数大的数while (arr[i] pivot i j) i;if (i j){// 交换两个数在数组中的位置int temp arr[i];arr[i] arr[j];arr[j] temp;}}// 最终将基准数归位arr[begin] arr[i];arr[i] pivot;// 递归处理QuickSort(arr, begin, i - 1); // 继续处理左边的这里是一个递归的过程QuickSort(arr, i 1, end); // 继续处理右边的 这里是一个递归的过程
} 2.4 、算法分析 快速排序是不稳定排序之所比较快是因为相比冒泡排序每次交换是跳跃式的。每次排序的时候设置一个基准点将小于等于基准点的数全部放到基准点的左边将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换交换的距离就大的多了。因此总的比较和交换次数就少了速度自然就提高了。当然在最坏的情况下仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n²)它的平均时间复杂度为 O(n * log n)。和归并排序一样其在算法实现上采用了分治法与递归思想。
