排序(递进式讲解+动图演示+代码分析) |
您所在的位置：网站首页 › 递进式示意图 › 排序(递进式讲解+动图演示+代码分析) |
排序(递进式讲解+动图演示+代码分析)
|
前言
文章内容中的一些思想，基本都是在以前学习中感悟中得到。其实在刚开始接触排序算法时，感到也非常陌生，学思想的时候，感觉也就那么回事，但是学完没多久忘了。主要是算法思想太多，有的内容太过复杂，于是我总结了每个算法最根本的思想，通过这根本的思想去回忆起对应的算法。另外，在文章中某些有联系的算法，我还采用了递进式的讲解方式，把算法的缺点，优点，以及怎么优化，以及优化后的算法基本都展现了出来。这样也是帮助大家记忆时能有联系性，而不是一块一块地去记忆。值得注意的是文章中的图，确实花费了老大功夫，也是精髓所在。
纸上得来终觉浅，绝知此事要躬行。
只有你在看明白之后，能够多思考，多输出，这样才能扎扎实实，希望本篇文章能够帮助到大家。
1排序的基本概念
1.1 排序的定义
排序概念:重新排列表中的数据,使得表中的元素满足按关键字有序的过程。
算法的
稳定性: 排序完成之后,若表中
相同元素的相对位置没有发生改变。(即:没排序之前,A元素在B元素前,排完序之后,A元素还在B元素前,称这种算法是稳定的,反之。)
时间复杂度：算法中基本操作执行的次数
空间复杂度：对一个算法在运行过程中临时占用存储空间大小的一个量度。
排序分类:在排序过程中,根据数据元素是否都在内存中,将排序分为内部排序与外部排序两个大类。
内部排序:排序期间元素全部放在内存中
外部排序:排序的时候元素无法全部同时存放在内存中,排序的时候元素不断地在内外存之间移动。
2 插入排序
基本思想:每次将一个待排序的元素插入前面已经排好的子序列,使得这个子序列保持有序。
2.1直接插入排序
无序序列向有序序列排序后再插入 ①算法思想: 
②动图演示: 
③代码展示： static void insertSort(int[] arr){ for (int i = 1; i < arr.length; 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; } } public static void main(String[] args) { int[] arr={53,56,63,90,120,1}; System.out.println("未排序的数组："); for (int i : arr) { System.out.print(i+" "); } // 开始给原有的数组进行排序 insertSort(arr); System.out.println(); System.out.println("已排序的数组："); for (int i : arr) { System.out.print(i+" "); } }④算法性能: 时间复杂度: O( 空间复杂度: O(1) 仅使用了常数个辅助单元 稳定性: 稳定 (在比较的时候出现相同值的元素,就停止比较了) 使用性:适用于顺序存储和链式存储 2.2 折半插入排序无序序列向有序序列跳着排序后再插入 不难看出,直接插入比较次数很大,相当于是挨个比较。直接插入排序是：边比较边插入。下面引出一个算法将比较和插入操作分离。 先折半查找确定各元素待插入的位置，再统一移动数据。引出折半插入排序的目的在于 减少比较次数,相当于跳着比较，但是 元素移动的次数没有改变。①算法（伪代码）： void InsertSort(ElemType A[], int n) { int i, j, low, high, mid; for (i = 2; i = high + 1; --j) A[j + 1] = A[j]; A[high + 1] = A[0]; //统一后移元素，空出插入位置//插入操作 } } }②算法性能： 时间复杂度：O（ 空间复杂度：O（1） 稳定性：稳定 （13行代码中，在大于0时才会跳转到左子表，相等的时候会跳转到右边。注意此时升序排列） 2.3 希尔排序增量之间排序，增量递减。 直接插入排序时，若待排序序列为正序时，时间复杂度仅为O(n),可以看出 直插排序适用基本有序的的排序表和数据量不大的排序表。希尔排序就是基于这两点改进而来，仔细想一下，希尔排序在进行到最后一趟排序时，表基本有序了。①算法思想： 
②动图演示: 
③算法性能： 时间复杂度：O（ 空间复杂度：O（1） 稳定性：不稳定 在排序的过程中，相同值的元素的相对位置发生了改变。 3交换排序 基本思想：根据序列中两个元素的比较结果来对换这两个元素在序列中的位置。 3.1冒泡排序相邻元素两两比较，交换排序。 ①算法思想： 从后往前（或从前往后）两两比较相邻元素的值，若这两个元素的值未按照整个序列的排序，就交换这两个元素的位置。最终每次会确定一个元素的位置，持续n轮后，n个元素都找到属于自己的位置。 ②动图演示： 
③算法性能： 时间复杂度：O( 空间复杂度：O（1）（仅借用了常数个辅助单元） 稳定性：稳定 （值相等的元素不进行交换） 3.2 快速排序(重点)Quick Sort 平均性能最优排序算法。理解起来有点难。①算法思想： 首先确定第一个元素为基准元素 pivot。 然后用high指针指向的元素和pivot作比较，high值大（这是正常的，不需要交换），high指针--，再次比较，若此时high值比pivot值小时，交换两个元素的位置。（换完位置就要变换指针）接着用low指针指向的元素和pivot比较，low值小（这是正常的，不需交换），low++，再次比较，若此时low值比pivot值大时，交换两个元素的位置。 接着这次变换指针，重复上面的步骤，直到确定基准元素的最终的位置，这是一趟排序。 
若基准元素不是边界元素时，以基准元素为中心，可以把整个序列拆分成两个子序列。然后再对两个子序列进行上诉过程。 ②算法代码： @Test public void method_01(){ int[] arr={20,23,455,23,1,55,66,1,24,408}; quickSort(arr,0,arr.length-1); // Arrays.sort(arr); 其实数组工具类中的排序方法也是用的快排思想 System.out.println(Arrays.toString(arr)); } void quickSort(int[] arr ,int low,int high){ if (low |
)
，但是在移动元素的却是O（【本文地址】