『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

1.排序的分类

排序分为两类:

内部排序:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。

外部排序:若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。

一般来说,外部排序只有数据量极大时会使用,一般情况下排序指的都是内部排序。

image-20200627110216492

2.空间复杂度

1.类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。

2.空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

3.在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间。

3.排序的稳定

待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中arr[i]领先于arr[j](即i<j)。若在排序后的序列中arr[i]仍然领先于arr[j],则称所用的方法是稳定的。

比如int数组[1,1,1,6,4]中arr[0],arr[1],arr[2]的值相等,在排序时不改变其序列,则称所用的方法是稳定的。

稳定的排序:冒泡排序,插入排序,归并排序,基数排序,计数排序

不稳定的排序:快速排序,希尔排序,选择排序,堆排序

稳定性设计到排序的现实意义,举个例子:

例如要排序的内容是一组原本按照价格高低排序的对象,如今需要按照销量高低排序,使用稳定性算法,可以使得想同销量的对象依旧保持着价格高低的排序展现,只有销量不同的才会重新排序。

更多关于稳定性的理解可以参考这个

4.各排序时间复杂度概览 排序法 平均时间 最差情形 是否稳定 优先选择条件
冒泡排序   O(n^2)   O(n^2)   稳定   n小时较好  
交换排序   O(n^2)   O(n^2)   不稳定   n小时较好  
选择排序   O(n^2)   O(n^2)   不稳定   n小时较好  
插入排序   O(n^2)   O(n^2)   稳定   大部分已排序时较好  
基数排序   O(logRB)   O(logRB)   稳定   B是真数(0-9),R是基数(个十百)  
希尔排序   O(nlogn)   O(ns)1<s<2   不稳定   s是所选分组  
快速排序   O(nlogn)   O(n2)   不稳定   n大时较好  
归并排序   O(nlogn)   O(nlogn)   稳定   n大时较好  
堆排序   O(nlogn)   O(nlogn)   不稳定   n大时较好  
一、冒泡排序

冒泡排序是一种简单的排序算法,它也是一种稳定排序算法。其实现原理是重复扫描待排序序列,并比较每一对相邻的元素,当该对元素顺序不正确时进行交换。一直重复这个过程,直到没有任何两个相邻元素可以交换,就表明完成了排序。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

要对10,-1,8,3这四个数进行排序:

第一次排序:

-1,10,8,3 //比较10和-1,逆序则交换

-1,8,10,3 //比较10和8

-1,8,3,10 //比较10和3

第一次排序结束,确定了四个数里最大的数的位置

第二次排序:

-1,8,3,10 //比较-1和8,不逆序所以不需要移动

-1,3,8,10 //比较8和3

由于已经确定了10为最大数,所以只需要比较到倒数第二位。

第二次排序结束,确定了第二大的数的位置

第三次排序:

-1,3,8,10 //比较-1和3

由于已经确定了第三和第四大的数,所以只需要比较到倒数第三位。

第三次排序结束,确定了第三大的数,故第一大的数也随之确定

2.思路

比较相邻的元素。如果第一个比第二个大,就交换它们两个;

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

针对所有的元素重复以上的步骤,除了最后一个;

重复步骤1~3,直到排序完成。

3.实现代码 /** * 输入一串无序数组,对其进行冒泡排序 * @param arr * @return */ public static int[] sort(int[] arr) { //如果某次排序不发生交换,说明上一次排序前已经为有序 boolean isChange = false; //根据数组长度决定一共需要排序几次 int round = arr.length - 1; for (int i = 0; i < round; i++) { //每次排序需要对比到第几位 for (int j = 0; j < round - i; j++) { //对比大小 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; //发生交换 isChange = true; } } //判断本次排序是否发生交换 if (!isChange) { System.out.println("第" + (i + 1) + "次排序无交换,第" + i + "次排序已为有序!"); return arr; }else { isChange = false; } System.out.println("第" + (i + 1) + "次排序:" + Arrays.toString(arr)); } return arr; } //{-1, 52, 9, 13, -5, 7}排序运行结果 第1次排序:[-1, 9, 13, -5, 7, 52] 第2次排序:[-1, 9, -5, 7, 13, 52] 第3次排序:[-1, -5, 7, 9, 13, 52] 第4次排序:[-5, -1, 7, 9, 13, 52] 第5次排序无交换,第4次排序已为有序! 二、选择排序

选择排序,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

选择排序(select sorting)也是一种简单的排序方法。
它的基本思想是:
第一次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换;
第二次从arr[1]~arr[n-1]中选取最小值,与arr[1]交换;
第三次从arr[2]~arr[n-1]中选取最小值,与arr[2]交换;

第i次从arr[i-1]~arr[n-1]中选取最小值,与arr[i-1]交换;

第n-1次从arr[n-2]~arr[n-1]中选取最小值,与arr[n-2]交换,
总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

2.思路

需要进行n-1轮排序

若要为第i个数排序,就先默认第i个元素为最小数,记录其大小和下标

接着从第i+1到第n个数开始依次比较,如果有数小于最小数,则用该数替换原最小数和其下标

第i轮比较结束后,让找出的最小数与第i个数交换位置

3.代码实现 /** * 输入一串无序数组,对其进行选择排序 * @param arr * @return */ public static int[] sort(int[] arr) { for (int i = 0; i < arr.length -1; i++) { //用于存放每次选择中最小数的下标,最小值默认为第一个数为i int minNumIndex = i; //从(i+1,arr.length)的范围中筛选最小的数 for (int j = i + 1; j < arr.length; j++) { //如果范围内有数比现有minNum小,则替换下标 if (arr[j] < arr[minNumIndex]) { minNumIndex = j; } } //一次选择结束,将(i+1,arr.length)的范围中的最小数与arr[i]交换位置 int temp = arr[minNumIndex]; arr[minNumIndex] = arr[i]; arr[i] = temp; System.out.println("第" + (i + 1) + "轮:" + Arrays.toString(arr)); } return arr; } //{-1, 52, 9, 13, -5, 7}排序运行结果 第1轮后:[-5, 52, 9, 13, -1, 7] 第2轮后:[-5, -1, 9, 13, 52, 7] 第3轮后:[-5, -1, 7, 13, 52, 9] 第4轮后:[-5, -1, 7, 9, 52, 13] 第5轮后:[-5, -1, 7, 9, 13, 52] 4.与冒泡排序比较

同样对长度80000的数字进行排序,选择排序比冒泡排序快不少,原因在于选择排序每次排序只移动指针,找到位置后才进行一次元素交换,而冒泡需要多次交换。

换句话说,要排序的数组越长,冒泡每次排序元素要移动的次数就越多,与选择排序的差距就越明显。

这个同样能解释希尔排序的两种实现方式的速度差距。

//冒泡排序交换值,交换n次值 temp = arr[j]; arr[j + gap] = temp; arr[j] = arr[j + gap] //插入排序交换值,交换n次指针 arr[j] = arr[j - gap] //然后交换1次值 temp = arr[j]; arr[j + gap] = temp; arr[j] = arr[j + gap] 三、插入排序

插入排序,是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

有数组{5,2,4,6,1,3}要进行排序,

从第二位往前看,5比2大,且5为第一个数,于是5后移,把2插入5前。现在是{2,5,4,6,1,3}

从第三位往前看,5比4大,于是5后移,继续往前看,2比4小,所以把4插入原先5的位置。现在是{2,4,5,6,1,3}

从第四位往前看,4比6小,于是6就不动了。现在是{2,4,5,6,1,3}

从第五位往前看,6比1小,于是6后移,继续往前看,5比1小,5后移,继续往前看.....2比1小,2后移,又2为第一个数,于是把1插入原本2的位置。现在是{1,2,4,5,6,3}

从第六位往前看,6比3小,于是6后移,继续往前看,.....3比2大,于是把3插入原先4的位置。排序完成。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

2.思路分析

从第一个元素开始,该元素可以认为已经被排序;

取出下一个元素,在已经排序的元素序列中从后向前扫描;

如果该元素(已排序)大于新元素,将该元素移到下一位置;

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置后;

重复步骤2~5。

3.代码实现 /** * 输入一串无序数组,对其进行插入排序 * @param arr * @return */ public static int[] sort(int[] arr) { //需要从第二位开始,避免i-1出现控制针 for (int i = 1; i < arr.length; i++) { //指向当前插入位置前一个元素的指针 int pre = i - 1; //当前处理元素的值 int val = arr[i]; // 让比当前元素大的元素不断的后移,直到到头了或者找到了比当前元素小的元素 while (pre >= 0 && arr[pre] > val) { //前一个元素往后移 arr[pre + 1] = arr[pre]; //继续往前移动 pre--; } //跳出循环时即找到了当前元素的正确插入位置 //将该位置的值赋成处理元素的值 arr[pre + 1] = val; System.out.println("第" + (i + 1) + "轮:" + Arrays.toString(arr)); } return arr; } //{-1, 52, 9, 13, -5, 7}排序运行结果 第2轮:[-1, 52, 9, 13, -5, 7] 第3轮:[-1, 9, 52, 13, -5, 7] 第4轮:[-1, 9, 13, 52, -5, 7] 第5轮:[-5, -1, 9, 13, 52, 7] 第6轮:[-5, -1, 7, 9, 13, 52] 四、希尔排序

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。

希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少,每组包含的关键词越来越多, 当增量减至1时,整个文件恰被分成一组,算法便终止。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

2.思路

将数组除于2进行分组,得到gap组数字

对gap组数字进行插入排序,由于数据共分为gap组,所以同一组相邻的数字在数组中的位置总是相隔gap

遍历gap组数字,表现在数组上就是从gap遍历到arr.length

3.代码实现

有两种实现思路,一种是交换法,一种是移位法

先说结论:移位法比交换法快,原因在于:

交换法思路有点类似于冒泡排序,需要不断的比较并交换数值,

而移位法即选择排序,仅仅遍历赋值后移动指针,找到插入位置后,再把元素插入到有序表,而不是多次交换加入有序表。

//交换法交换n次值 temp = arr[j]; arr[j + gap] = temp; arr[j] = arr[j + gap] //位移法移动n次指针后只交换一次值 arr[j] = arr[j - gap] 3.1交换法实现 /** * 输入一串无序数组,对其进行希尔排序 * 注意,此方法为移位法 * @param arr * @return */ public static int[] sort(int[] arr) { int temp = 0; int count = 0; // 将数组每次对半分分成多组,组数逐渐缩小 // gap为每次分组后的同组元素的间隔,比如分成5组,那同组元素间隔即为5,即位置是i和i+5的元素是一组 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 从第gap个元素开始,逐步遍历其所在的组,即从第一组开始向后遍历 // 第gap个元素即为第一组的最后一个元素,也就是i即表示某组的最后一个位置 for (int i = gap; i < arr.length; i++) { // 接着遍历同组元素,即一组有几个元素就遍历几次 // j=i-gap即获得第某组的倒数第二个元素位置 // 向前遍历,每隔gap个元素就对比一次大小 for (int j = i - gap; j >= 0; j = j - gap) { //如果当前元素大于后一个元素,就交换位置 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } System.out.println("第" + (++count) + "轮:" + Arrays.toString(arr)); } return arr; } //{-1, 52, 9, 13, -5, 7}排序运行结果 第1轮:[-1, -5, 7, 13, 52, 9] 第2轮:[-5, -1, 7, 9, 13, 52] 3.2 移位法实现

下面是通过移位法实现的排序,〔 广州股票配资〕,比交换法更快更稳定:

/** * 输入一串无序数组,对其进行希尔排序 * 注意,此方法为移位法 * @param arr * @return */ public static int[] sortByMove(int[] arr) { int count = 0; // 将数组每次对半分分成多组,组数逐渐缩小 // gap为每次分组后的同组元素的间隔,比如分成5组,那同组元素间隔即为5,即位置是i和i+5的元素是一组 for (int gap = arr.length / 2; gap > 0; gap /= 2) { //从第gap个元素开始,逐个对其所在组进行插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; //如果某组最后一个元素比前一个元素小 if (arr[j] < arr[j - gap]) { //将同组元素不断后移,直到该元素找到位置或者到头为止 while (j - gap >= 0 && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j = j - gap; } //当找到位置时插入元素 arr[j] = temp; } } System.out.println("第" + (++count) + "轮:" + Arrays.toString(arr)); } return arr; } 五、快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

先选择一个中间位置数11,分别将数组中比11大和比11小的数放到左右两个数组中

对两个数组分别选一个中间位置数,也就是5和21,各自再根据比中间数小或者比中间数大再次分为两个数组。以此类推

2.思路

把长度为n的输入序列分成两个长度为n/2的子序列

对这两个子序列分别采用归并排序;

将两个排序好的子序列合并成一个最终的排序序列

对左支和右支可通过递归实现排序

3.代码实现 public static int[] sort(int[] arr) { sort(arr, 0, arr.length - 1); return arr; } /** * 输入一串无序数组,并根据给定的左右指针对指定的范围其进行排序 * @param arr * @param left * @param right * @return */ public static int[] sort(int[] arr, int left, int right) { //左右指针 int l = left; int r = right; //找到中间数 int pivot = arr[(left + right) / 2]; //用于元素交换的临时变量 int temp; //将比中间数小的放左边,比中间数大的放右边 while (l < r) { // 从左往右遍历,寻找比中间数大的数 while (arr[l] < pivot) { l++; } // 从右往左遍历,寻找比中间数小的数 while (arr[r] > pivot) { r--; } // 如果l > r,即左指针右指针都越过了中间数,说明两边数都已经有序 // 如果l = r,即可能存在多个与中间数同值的元素的情况下,左右指针一起指向了同一边的同一个元素,也说明两边数都已经有序 if (l >= r) { break; } //交换元素 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后,发现现在右侧有一个与中间数相同的数,右指针前移一位 if (arr[l] == pivot) { r -= 1; } //如果交换完后,发现现在左侧有一个与中间数相同的数,左指针后移一位 if (arr[r] == pivot) { l += 1; } } //防止死循环 if (l == r) { l += 1; r -= 1; } //向右递归 if (left < r) { sort(arr, l, right); } //向左递归 if (right > l) { sort(arr, left, r); } return arr; } 六、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

我们以上图最后一次合并为例:

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

以上多个有序数组间的合并需要进行多次,通过递归完成

2.思路

把长度为n的数组分成两个长度为n/2的子数组;

如果子数组仍然长度大于1,就重复步骤1直到所有数组都被拆分完毕

将拆分后的元素两两合并为一个有序数组,然后相邻两个数组A,B进行合并:

创建一个新数组,然后遍历B数组并与A数组第一位进行比较,如果该数字比A数组第一小则放入新数组第一位

否则将A数组第一位放入新数组

重复上面步骤3直到A,B数组所有元素都有序放入新数组,即合并完成

重复步骤3,直到所有数组都最终都被合并为一个有序数组

3.代码实现 /** * @Author:黄成兴 * @Date:2020-06-29 21:45 * @Description:归并排序 */ public class MergeSort { public static void main(String[] args) { int arr[] = {8, 4, 5, 7}; System.out.println(Arrays.toString(sort(arr))); } public static int[] sort(int[] arr) { int temp[] = new int[arr.length]; return sort(arr, 0, arr.length - 1, temp); } /** * 合并排序 * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param right 右边索引 * @param temp 临时存储的中转数组 */ public static int[] sort(int[] arr, int left, int right, int[] temp) { if (left < right) { //获取中间索引 int mid = (left + right) / 2; //向左递归分解 sort(arr, left, mid, temp); //向右递归分解 sort(arr, mid + 1, right, temp); // 先左遍历到最左边,然后向右遍历,当l=r时触发排序 merge(arr, left, mid, right, temp); } return arr; } /** * 合并的方法 * * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 临时存储的中转数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { //左边有序序列的初始索引 int i = left; //中间索引 int j = mid+1; //temp的索引 int t = 0; //先把左右两边有序的数据按照规则填充到temp数组,直到左右两边的有序序列,有一边处理完毕为止 while (i <= mid && j <= right) { //如果左边的有序序列的当前元素小于等于右边有序序列的当前元素 if (arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else { //否则将右边有序序列的当前元素填充到temp数组 temp[t] = arr[j]; t += 1; j += 1; } } //左边的有序序列还有剩余的元素,就全部填充到temp数组 while (i <= mid) { temp[t] = arr[i]; t += 1; i += 1; } //右边的有序序列还有剩余的元素,就全部填充到temp数组 while (j <= right) { temp[t] = arr[j]; t += 1; j += 1; } //将temp数组里的有序元素拷贝回arr数组 //从左边开始拷贝, 注意:不是每次都拷贝所有 t = 0; int tempLeft = left; //第一次合并:templeft = 0,right = 1。 第二次合并:templeft = 2,right = 3。 最后一次:templeft = 0,right = 7 while (tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } } 七、基数排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

1.举个例子

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

『股票配资onemiao』煤层气概念股数据结构与算法(八):排序

2.思路

取得数组中的最大数,并取得位数

准备一个长度为10,内部一位数组长度为arr.length的二维数组,可以理解为10个高度为arr.length的桶

遍历数组,根据数组中个位数决定要放在哪个桶,即如果个位数为1就放入1号桶,为2就放入2号桶,直到数组所有元素分配完毕

遍历桶将桶中数字放回原数组,然后清空桶。即完成了个位数的排序

重复步骤3和步骤4,但是排序依据从个位数换成十位数,然后百位数.....以此类推,直到数组最大位数

3.代码实现 package com.huang.example.sort; import java.util.Arrays; /** * @Author:黄成兴 * @Date:2020-06-30 21:39 * @Description:基数排序 */ public class RadixSort { public static void main(String[] args) { int[] arr = {53, 3, 542, 748, 14, 214 }; System.out.println("最大位数:" + getMaxDigit(arr)); System.out.println(Arrays.toString(sort(arr))); } /** * 获取数组中的最大数的位数 * @param arr * @return */ public static int getMaxDigit(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return String.valueOf(max).length(); } public static int[] sort(int[] arr) { //设置二维数组用于表示桶 //第一层数组下标即表示存放某数位为x的数字的桶,比如下标为2的桶用于存放个位数为2的数字;下标为0的桶用于存放十位数为0的数字 //第二层数组即表示桶高度 int[][] bucket = new int[10][arr.length]; //表示某个桶内用几个元素,比如bucketElementCount[0]即表示bucket[0]桶有几个元素 //由于数字下标从0开始,所以这同时也表示了桶下一个元素的插入下标,比如bucketElementCount[0]=1,就意味着bucket[0]下一个元素应该插到bucket[0][1]去 int[] bucketElementCount = new int[10]; //最大数有几位就循环排序几次 for (int i = 0, n = 1; i <= getMaxDigit(arr); i++, n *= 10) { //遍历元素并归类到桶中 for (int j = 0; j < arr.length; j++) { //获取元素某数位的数字 //根据遍历,获取数字的个位,十位数,百位数...... int digitOfElement = arr[j] / n % 10; //将其归类到桶中 bucket[digitOfElement][bucketElementCount[digitOfElement]] = arr[j]; //提高桶高度 bucketElementCount[digitOfElement]++; } //按顺序将每一个桶中元素取出并放入原集合 int index = 0; for (int k = 0; k < bucketElementCount.length; k++) { //如果桶中有元素就取出 if (bucketElementCount[k] != 0) { //遍历桶中元素并放入数组 for (int l = 0; l < bucketElementCount[k]; l++) { arr[index++] = bucket[k][l]; } } //清空桶 bucketElementCount[k] = 0; } } return arr; } } 4.基数排序注意事项:

基数排序是典型的空间换时间,当排序的数字过多的时候可能会发生OutOfMemoryError(实测八千万时报错)

基数排序要排负数的时候需要加以改进:

将数组中的负数单独摘出并取绝对值后进行排序,然后倒序插入排序完的整数数组,并且在插入过程加上负号

八、堆排序

参照二叉树部分