排序的概念及其引用:

排序的概念:

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的;

画图说明:

排序前A在B前面,排序后说明该排序稳定,如果排序后B在A前面则说明不稳定。

内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

八大排序我们一般将其分为五类,分别为:

一:  插入排序

1. 直接插入排序

2. 希尔排序

二: 选择排序

1.直接选择排序

2.堆排序

三: 交换排序

1. 冒泡排序

2. 快速排序

四: 归并排序

五:基数排序

插入排序:

直接插入排序:

基本思路:

思路:从第二个数开始,假设此数为 tmp ,逐个往前进行比对,如果前数大于 tmp ,就将前数值赋值到 tmp 处,然后继续往前比对,直到找到小于或等于 
tmp 的数(或者比对至数据首)就停止,最后将 tmp 的值赋值到此处就行了

动图演示:

代码:
public void insertSort(int[] array) { if (array.length == 0) { return; } for
(int i = 1; i < array.length; i++) { int temp = array[i]; int j = i - 1; for (
; j >= 0 ; j--) { if (array[j] > temp) { array[j + 1] = array[j]; } else {
break; } } array[j + 1] = temp; } }
 直接插入排序总结:

1. 集合元素越接近有序,时间效率越高

2. 时间复杂度: O(N^2)

3. 空间复杂度: O(1)

4. 稳定性: 稳定 

希尔排序:

前言:

既然同为插入排序,那必然是有共同点的。

希尔排序是建立在直接插入排序基础上,经过优化的插入排序。

希尔排序分为两步:

* 1、预排序,使得数据尽可能接近有序
* 2、直接插入排序,最后调用一次直接插入排序,快速的完成排序
基本思路:

思路:预排序是通过区间划分实现的,假设当前区间为 gap,那么 1、1+gap*n 可以分成一组,同理2、3、4
 都可以分,将这些组分别进行直接插入排序(数据少,效率高)。每完成一次分组排序,gap 就会缩小,直到 gap 为1时,进行一次直接插入排序,整个希尔排序
就完成了

代码如下:
public static void shellSort(int[] array) { int gap = array.length; while (gap
> 1) { shell(array,gap); gap /= 2; } //整体进行插入排序 shell(array,1); } public static
void shell(int[] array,int gap) { for (int i = 1; i < array.length; i++) { int
temp = array[i]; int j = i - gap; for ( ; j >= 0 ; j-= gap) { if (array[j] >
temp) { array[j + gap] = array[j]; } else { break; } } array[j + gap] = temp; }
}
动图演示:

预排序:

 直接插入排序:

希尔排序总结:

1. 希尔排序的时间复杂度要用到高数中的知识,“根据大量的数据的得到了局部的结论...”,我们直接记答案即可:O(N^1.25)

2. 空间复杂度: O(1);

我们仅仅只创建了一个gap

3. 稳定性: 不稳定;

我们在排序过程中gap会有多次的改变,不同的组别中可能会发生交换现象。

选择排序:

直接选择排序:

基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完

代码:
//选择排序 public static void selectSort(int[] array) { for (int i = 0; i <
array.length; i++) { int minIndex = i; for (int j = i + 1; j < array.length;
j++) { if(array[j] < array[minIndex]) { minIndex = j; } } int temp = array[i];
array[i] = array[minIndex]; array[minIndex] = temp; } }
如果像这样去遍历的话,时间复杂度为O(N^2)不算是个很优解我们可以考虑对此进行优化

优化:每次遍历选最大与最小,分别与 end 值和 begin 值交换

动图演示:

 直接选择排序总结:

1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

堆排序:

我们之前也介绍过堆排序,PriorityQueue本质就是个小根堆,这里就不过多介绍了。

思路:堆排序用到了堆的知识,如果想排升序的话建大堆,因为大堆中堆顶是最大值,将堆顶值与堆低值交换后,执行向下调整,使其再次变为大堆,就这样反复交换、调整,
堆排序就完成了。
/** * 堆排序 * @param array 目标数组 */ public static void heapSort(int[] array) {
createBigHeap(array); int end = array.length - 1; while (end > 0) {
swap(array,0,end); shiftDown(array,0, end); end--; } } public static void
createBigHeap(int[] array) { //父下标 从倒数第二层开始 int parent = (array.length - 1 -1)
/ 2; for (; parent >= 0 ; parent-- ) { shiftDown(array,parent, array.length); }
} public static void shiftDown(int[] array,int parent,int len) { int child =
2*parent + 1; while (child < len) { if (child + 1 < len && array[child] <
array[child + 1]) { child++; } if (array[child] > array[parent]) { swap(array,
parent, child); parent = child; child = 2 * parent + 1; } else { break; } } }
private static void swap(int[] array,int i,int j) { int tmp = array[i];
array[i] = array[j]; array[j] = tmp; }
向上调整动图演示:

 堆排序总结:

1. 堆排序使用堆来选数相对于直接插入排序,效率就高了很多。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(1)
4. 稳定性:不稳定

本文只是排序的上半部分,涉及的排序思想都还算简单,下一篇文章中将会介绍排序大哥:快速排序,知识点很难敬请期待吧。

技术
今日推荐
PPT
阅读数 84
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信