赞
踩
目录
参考文章:
十大经典排序算法最强总结: 十大经典排序算法最强总结(含JAVA代码实现) - 郭耀华 - 博客园
排序算法总结 : 排序算法总结 | 菜鸟教程
术语说明
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
另外参考:排序算法(一) —— 冒泡排序 - Gerrard_Feng - 博客园
1.1 算法描述
1.2 动图演示
1.3 代码实现
内层循环每比较完一次后,最后面的已经是有序的,所以无需在比较,因此内层循环次数是 array.length - 1 - i
- int[] Bubble_Sort(int[] array)
- {
- if (array.length == 0)
- return array;
- // 外层for循环控制循环次数
- for (int i = 0; i < array.length; i++)
- {
- // 内层for循环控制相邻的两个元素进行比较
- for (int j = 0; j < array.length - 1 - i; j++)
- {
- if (array[j] > array[j + 1])
- {
- int temp = array[j + 1];
- array[j + 1] = array[j];
- array[j] = temp;
- }
- }
- }
- return array;
- }
1.4 算法分析
最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)
解释:冒泡排序的最优的时间复杂度为O(n),其实这是在代码中使用一个标志位来判断是否已经排序好的,是冒泡排序的优化版,如果元素已经排序好,那么循环一次就直接退出。
选择排序可以看做是冒泡排序的改进,是表现最稳定的排序算法之一,因为无论序列是怎样的都要比较n(n-1)/2次,所以时间复杂度都是O(n2), 最好、最坏、平均时间复杂度也都为O(n²),所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧,需要一个临时变量用来交换数组内数据位置,所以空间复杂度为O(1)。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
另外参考:排序算法(二) —— 选择排序 - Gerrard_Feng - 博客园
2.1 算法描述
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
2.2 动态图演示
2.3 代码实现
- int[] selectionSort(int[] array) {
- for (int i = 0; i < array.length - 1; i++) {
- // 最小元素坐标, 每次循环开始,重置坐标
- int minIndex = i;
- for (int j = i + 1; j < array.length; j++) {
- if (array[j] < array[minIndex]) //找到最小的数
- minIndex = j; //将最小数的索引保存
- }
- // 判断第一个是不是最小值,是的话可以不用交换
- if (i != minIndex) {
- int temp = array[minIndex];
- array[minIndex] = array[i];
- array[i] = temp;
- }
- }
- return array;
- }
2.4 算法分析
最佳情况:T(n) = O(n2) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
3.1 算法描述
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
3.2 动图演示
3.3 代码实现
- //在排序之前我们需要搞清一个思路,新插入一个数据的时候,排序过后的数组(前i个元素)都是
- //从小到大排列好的,所以我们需要从后往前查找,直到找到比我们要插入的数字还小的
- //值。这个时候我们需要一个变量j作为标识
- int[] insertionSort(int[] array) {
-
- if (array == null || array.length < 2) {
- return;
- }
-
- for (int i = 0; i < array.length - 1; i++) {
- //前 i 个元素已经排序好, 第 i+1 个元素是要插入的元素
- int cur = array[i + 1];
- //j的值也就是cur要插入的位置
- //倒序遍历,不断移位
- for(int j = i; j >= 0; j--) {
- if(cur < array[j]){
- array[j+1] = array[j];
- }else{
- //数据已经插入,就不需要再循环了
- array[j + 1] = cur;
- break;
- }
- }
- }
- return array;
- }
更加简练的代码:
- void insert_sort(int array[],int lenth){
- int temp;
- for(int i=0;i<lenth-1;i++){
- for(int j=i+1;j>0;j--){
- if(array[j] < array[j-1]){
- temp = array[j-1];
- array[j-1] = array[j];
- array[j] = temp;
- }else{ //不需要交换
- break;
- }
- }
- }
- }
3.4 算法分析
最佳情况:T(n) = O(n) 最坏情况:T(n) = O(n2) 平均情况:T(n) = O(n2)
如果序列是完全有序的,插入排序只要比较n次,无需移动时间复杂度为O(n),如果序列是逆序的,插入排序要比较O(n²)和移动O(n²) ,所以平均复杂度为O(n²),最好为O(n),最坏为O(n²),排序过程中只要一个辅助空间,所以空间复杂度O(1)。
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
4.1 算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
4.2 动图演示
4.3 代码实现
- void quickSort(int a[],int _left_,int _right_)
- {
- int left = _left_;
- int right = _right_;
- int temp = a[left]; //每次把最左边的元素left当做基准,这里必须是left,注意!!!!
- if(left >= right)
- return;
- // 从左右两边交替扫描,直到left = right
- while(left != right)
- {
- while(right > left && a[right] >= temp)
- right--; //从右往左扫描,找到第一个比基准元素小的元素
- a[left] = a[right]; //找到后直接将a[right]赋值给a[l],赋值完之后a[right],有空位
-
- while(left < right && a[left] <= temp)
- left++; //从左往右扫描,找到第一个比基准元素大的元素
- a[right] = a[left]; //找到这种元素arr[left]后,赋值给arr[right],上面说的空位。
- }
- a[left] = temp; //把基准插入,此时left与right已经相等
- /*拆分成两个数组 s[0,left-1]、s[left+1,n-1]又开始排序 */
- quickSort(a, _left_, left-1); //对基准元素左边的元素进行递归排序
- quickSort(a, right+1, _right_); //对基准元素右边的进行递归排序
- }
一个变化
- void quicksort(int[] a,int left, int right) {
- int i, j, t, temp;
- if(left > right)
- return;
- temp = a[left]; //temp中存的就是基准数
- i = left;
- j = right;
- while(i != j) { //顺序很重要,要先从右边开始找
- while(a[j] >= temp && i < j)
- j--;
- while(a[i] <= temp && i < j)//再找右边的
- i++;
- if(i < j)//交换两个数在数组中的位置
- {
- //出现左边大于基准且右边小于基准的情况,两者交换后则满足左边小右边大
- t = a[i];
- a[i] = a[j];
- a[j] = t;
- }
- }
- //最终将基准数归位
- a[left] = a[i];
- a[i] = temp;
- quicksort(a,left, i-1);//继续处理左边的,这里是一个递归的过程
- quicksort(a,i+1, right);//继续处理右边的 ,这里是一个递归的过程
- }
4.4 算法分析
最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn)
当分区选取的基准元素为待排序元素中的最大或最小值时,为最坏的情况,时间复杂度和直接插入排序的一样,移动次数达到最大值
max = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) 此时最好时间复杂为O(n2)
当分区选取的基准元素为待排序元素中的"中值",为最好的情况,时间复杂度为O(nlog2n)。
快速排序的空间复杂度可以理解为递归的深度,而递归的实现依靠栈,平均需要递归logn次,所以平均空间复杂度为O(log2n)。
当待排序元素类似[6,1,3,7,3]且基准元素为6时,经过分区,形成[1,3,3,6,7],两个3的相对位置发生了改变,所是快速排序是一种不稳定排序。
时间复杂度分析: 快速排序时间复杂度为O(n×log(n))的证明 - Never say Ever - 博客园
快速排序优化 : 快速排序算法优化_ytusdc的博客-CSDN博客_快速排序算法优化
4.4 算法分析
最佳情况:T(n) = O(nlog2 n) 最坏情况:T(n) = O(nlog2 n) 平均情况:T(n) =O(nlog2n)
相关文章:归并排序 - 简书
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
5.1 算法描述
5.2 动图演示
上个更明了点的
下面一种是比较好理解的,原理如下(假设序列共有n个元素)
- private void sort(int[] array, int left, int right) {
- if (left < right) {
- int mid = (left + right) / 2;
- sort(array, left, mid);
- sort(array, mid + 1, right);
- Merge(array, left, mid, right);
- }
- }
-
-
- //C++ 版本 递归实现
- /*********************函数参数说明**********************
- 传入参数:需要排序数组的首地址 int* array
- 第一个已排序序列的起始索引 int start,第一个已排序序列的终止索引 int mid;
- 第二个已排序序列的起始索引 mid + 1,第二个已排序序列的终止索引 int end;
- 此处注意 newArray[i++] 这个操作是先 newArray[i],然后 i=i+1;
- ********************************************************/
-
- void Merge(int* array, int start, int mid, int end) {
- int[] newArray = new int[end - start + 1]; //第一步,申请空间,大小为两个排序序列之和
- int fistIndex = start; //第二步,设定两个待排序列的起始位置的索引
- int secondIndex = mid + 1;
- int i = 0; //所申请空间的索引
-
- //合并数组,直到两个序列中有一个到达终止位置
- while (fistIndex <= mid && secondIndex <= end) {
- if (array[fistIndex] <= array[secondIndex])
- newArray[i++] = array[fistIndex++];
- else
- newArray[i++] = array[secondIndex++];
- }
-
- // 此处 fistIndex <= mid 是因为,如果上面的while循环在 fistIndex = mid,把该值赋值给newArray时
- // fistIndex=fistIndex+1,不再是mid
- // 将左序列剩余的元素填充如临时序列
- while (fistIndex <= mid)
- newArray[i++] = array[fistIndex++];
-
- //将右序列剩余的元素填充如临时序列
- while (secondIndex <= end)
- newArray[i++] = array[secondIndex++];
-
- for (int j = 0; j < newArray.size(); ++j) //将合并且排序好的元素,复制到原来的数组中,释放临时数组空间
- array[start + j] = newArray[j];
-
- delete[] newArray;
- }
5. 4 算法分析
最佳情况:T(n) = O(n) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)
分析参考:排序算法(六) —— 归并排序 - Gerrard_Feng - 博客园
复杂度分析:排序算法(四):归并排序 - 腾讯云开发者社区-腾讯云
文章 :十大经典排序算法最强总结
看文章:希尔排序C++实现_zpznba的博客-CSDN博客_c++实现希尔排序
解释一下 从 i=gap 开始插入。
开始情况 i= gap,然后后面的 j-gap 等于0,因此就是比较a[gap] 和 a[0]的大小,后续进行 i++
就是遍历每一个元素进行比较
代码
- void shellSort(int a[],int len)
- {
- int insertNum = 0;
- int gap = len/2; // 步长初始化
- while(gap) // while gap>=1
- {
- //从 i = gap 开始插入
- for (int i = gap; i < len; ++i) // 分组,在每个子序列中进行插入排序
- {
- insertNum = a[i];//将当前的元素值先存起来方便后面插入
- int j = i;
- // a[j-gap] 取到的是 上一个 位置的值
- while (j >= gap && insertNum < a[j-gap])//寻找插入位置
- {
- a[j] = a[j - gap];
- j -= gap;
- }
- a[j] = insertNum;
- }
- gap = gap/2;
- }
- }
文章 :十大经典排序算法最强总结
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
7.1 算法描述
二叉树的性质先来了解下:
堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)
或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆)
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
对于任意一个完全二叉树来说,如果将含有的结点按照层次从左到右依次标号(二叉树结构),对于任意一个结点 i ,完全二叉树还有以下几个结论成立:
理解代码:i 节点的孩子节点为 2i +1和 2i+2 ;i节点的 父节点为:(i-1)/2;最后一个非叶子节点:n/2 - 1;下面的代码是实现的大根堆,把元素从小到大依次排序;
- /**
- * 堆排序算法
- */
- public static int[] HeapSort(int[] array) {
- int len = array.length;
- if (len < 1) return array;
- //1.构建一个最大堆
- buildMaxHeap(array);
- //2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
- while (len > 0) {
-
- //把大顶堆的根元素,放到数组的最后;换句话说,就是每一次的堆调整之后,都会有一个元素到达自己的最终位置
- swap(array, 0, len - 1);
- len--;
-
- // 元素交换之后,毫无疑问,最后一个元素无需再考虑排序问题了。
- // 接下来我们需要排序的,就是已经去掉了部分元素的堆了,这也是为什么此方法放在循环里的原因
- // 而这里,实质上是自上而下,自左向右进行调整的
-
- adjustHeap(array, 0, len);
- }
- return array;
- }
- /**
- * 建立最大堆
- */
- public static void buildMaxHeap(int[] array) {
- // 从最后一个非叶子节点开始向上构造最大堆
- // 在数组中第一个元素的索引是0
- // 第n个元素的左孩子为2n+1,右孩子为2n+2,
- // 最后一个非子节点位置在(n - 1) / 2
- int len = array.length();
-
- // i,指向完全二叉树中最后面的父节点, 然后一个个往前调整直到根结点
- for (int i = ((len - 1) / 2); i >= 0; i--) { //注意此处应该为 i = (len/2 - 1)
- adjustHeap(array, i, len);
- }
- }
- /**
- * 调整使之成为最大堆
- *
- * i 需要调整的堆元素索引,与它的子结点进行比较互换
- * len 当前需要调整的堆长度
- */
-
- public static void adjustHeap(int[] array, int i, int len) {
- int maxIndex = i; // 最大下标
-
- int left = 2 * i + 1; //左右孩子的索引,注意数组下标从0开始。
- int right = 2 * i + 2;
- //如果有左子树,且左子树大于父节点,则将最大索引指向左子树
- if (left < len && array[left] > array[maxIndex])
- maxIndex = left;
- //如果有右子树,且右子树大于父节点,则将最大索引指向右子树
- if (right + 1 < len && array[right] > array[maxIndex])
- maxIndex = right;
-
- // 如果父节点不是最大值,则将父节点与最大值交换,
- // 交换完成后,有可能会导致以a[i]为父节点形成的子树不满足堆的条件
- // 因此需要递归调整该子树
- if (maxIndex != i) {
- swap(array, maxIndex, i);
- adjustHeap(array, maxIndex);
- }
- }
7.4 算法分析
最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)
堆排序时间复杂度分析:
文章 :十大经典排序算法最强总结
复杂度分析: https://blog.csdn.net/YuZhiHui_No1/article/details/44594415
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。