一、前言及排序算法测试
1、前言
一般的，我们的排序只能对线性结构而言（大多数时候都是对数组进行排序）
数组的排序一般来说都是就地排序，要求不断地交换数组内部元素 最终得到有序的数组 如果需要新的数组来存储元素 空间复杂度就不再是O（1）
在正式进行排序之前 介绍几个概念：
时间复杂度：最好 平均 最坏
空间复杂度：最好 平均 最坏
排序的稳定性：比如说一个数组是{6，2，5，9，3，2，1}
在我们排序完成后 如果两个2的相对顺序没有改变，我们就说排序算法是具有稳定性！反之，排序算法就不具备稳定性
区间表示法：
为了让同学们更清晰的分辨元素和下标 本篇文章 元素类型使用long类型 下标自然就是int类型
区间表示一般分为两种：左闭右闭(size=right-left+1)、左闭右开(size=right-left)
最后说明一点 本篇文章的排序默认都是从小到大
2、测试的完备性
很多同学在手写完排序算法之后 不知道自己写的对不对 去leetcode提交的时候发现有时候即使自己写对了 但由于用时太长无法通过
在这里我们可以利用java自带的快排进行测试
测试的完备性问题：
1）正常的情况：{4，6，2，7，9，1，8，3}
2）特殊情况：
数组为空{}
数组已经有序{1，2，3，4，5，6，}
数组逆序{9，6，5，4，3，2，1}
数组全相等{1，1，1，1，1，1，1}
public class TestSort {
private static long[] 构建无序数组(int size) {
Random random = new Random();
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt();
}
return array;
}
private static long[] 构建全相等数组(int size) {
long[] array = new long[size];
Arrays.fill(array, 398);
return array;
}
private static long[] 构建有序数组(int size) {
Random random = new Random();
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = random.nextInt();
}
Arrays.sort(array);
return array;
}
private static long[] 构建逆序数组(int size) {
int half = size / 2;
long[] array = 构建有序数组(size);
for (int i = 0; i < half; i++) {
long t = array[i];
array[i] = array[size - 1 - i];
array[size - 1 - i] = t;
}
return array;
}
public static void main(String[] args) {
long[] array = 构建无序数组(4_0000);
long[] copy = Arrays.copyOf(array, array.length); // 完全复制一份数组出来
long b = System.currentTimeMillis();
//自己手写的排序赋值给array
long e = System.currentTimeMillis();
double ms = e - b;
double s = ms / 1000;
System.out.println("排序耗时: " + s);
Arrays.sort(copy); // 经过系统提供的排序算法排的序
if (Arrays.equals(array, copy)) {
System.out.println("排序算法正确");
} else {
System.out.println("排序算法错误");
}
}
}
二、冒泡排序
“冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。”
冒泡排序本质上是一种减治算法（减：问题的规模在不断减小 治：相同方式处理相同问题
对n个元素的数组进行冒泡，两相邻元素大者会被叫交换到后面，经过完整的一轮 就可以确定一个最大值到最后面
我们只需进行n-1轮就可以把所有当前无序数组中最大的数全部交换到后面，排序完成！
冒泡排序代码详解：
public static void bubbleSort(long[] nums){
//一个数组需要进行n-1轮冒泡就有序了（一个数的时候不需要冒泡）
int n=nums.length;
for (int i=0;i<n-1;i++){
//数组可以分为无序加有序
//一开始的无须数组：[0,n-i) 有序数组：[n-i,n)
//冒泡过程需要进行两两比较，所以需要进行无须数组的 size-1 次
for (int j=0;j<n-i-i;j++){
if (nums[j]>nums[j+1]){
swap(nums,j,j+1);
}
}
}
}
public static void swap(long[] nums,int i,int j){
long temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
** 测试40000无序结果：**
分析：当前这种冒泡排序的实现根本没有最好情况 和 最坏情况 每个for循环都必须要走一次****（即使数组已经有序）因此我们对它进行优化 优化的方式很简单 我们在每一轮冒泡前都可以加入一个标志 如果没有进行交换 那么我们就退出循环
总结：冒泡排序的时间复杂度是O(N^2) 空间复杂度是O(1) 具有稳定性
三、插入排序
1、直接插入排序
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。
我们把整个数组区间看为有序+无序 每次选择无序区间的第一个元素 在有序区间选择合适的位置进行插入
这就有点类似于我们斗地主 每接到一张牌我们都把他插到合适的位置，当然，我们只有一张牌的时候不需要考虑插入的位置
直接插入排序代码详解：
public static void insertSort(long[] nums){
//由于我们只有一个元素的时候不需要排序
//有序数组[0,i) 无序数组[i,nums.length)
for (int i=1;i<nums.length;i++){
int j=i;//记录无序数组的第一个元素 在有序数组中寻找合适的位置插入
long temp=nums[i];// 先暂存这个元素，然后之前元素逐个后移，留出空位
while (j>0&&nums[j-1]>temp){//j的前一个元素如果大于temp 那么我们就把nums[j-1]往后移
nums[j]=nums[j-1];
j--;
}
nums[j]=temp;//当我们退出循环的时候 就是[j-1]已经小于等于temp 那么j就是合适的需要插入的位置
}
}
插入排序的算法思想是：把无序往有序里插 所以 在数组基本有序或者数组很短的时候 l里边的while循环走的次数就越小 表现越优异
**总结：直接插入排序的时间复杂度 最好情况是O（N）（数组已经有序） 最坏和平均都是O(N^2) **
空间复杂度是O(1) 具有稳定性
2、希尔排序
“希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。”
上边我们说到过，直接插入在数组接近有序时性能更加优异 希尔排序是在插排上做的优化
我们在插入排序之前进行预处理 预处理虽然不能让元素有序，但可以让数据接近有序
把数组按固定的长度间隔做分组进行插排 各自在自己的组内进行插排
这里我们用到一个小tips 我们可以通过遍历数组 只需要控制好gap（间隔）就可以实现让数组元素在各自的组内进行插排
实现组内插排的代码如下：
public static void insertSortWithGap(long[] nums,int gap){
//我们确定需要分多少组后 各自组内的第一个元素默认是有序的 因此我们循环直接从gap开始
for (int i=gap;i<nums.length;i++){
int j=i;记录无序数组的第一个元素下标 在有序数组中寻找合适的位置插入
long temp=nums[i];// 先暂存这个元素，然后之前元素逐个后移，留出空位
while (j>=gap&&nums[j-gap]>temp){//nums[j-gap]元素如果大于temp 那么我们就把nums[j-gap]往后移
nums[j]=nums[j-gap];
j-=gap;
}
nums[j]=temp;
}
}
分组插排其实就是我们进行预处理的过程 在插排之前我们可能调整gap比较大进行分组插排 因为这样会让元素更接近它排序后的位置，gap不断地缩小 直至为1 进行插排 保证数组有序
希尔排序完整代码如下：
public static void insertSortWithGap(long[] nums,int gap){
//我们确定需要分多少组后 各自组内的第一个元素默认是有序的 因此我们循环直接从gap开始
for (int i=gap;i<nums.length;i++){
int j=i;记录无序数组的第一个元素下标 在有序数组中寻找合适的位置插入
long temp=nums[i];// 先暂存这个元素，然后之前元素逐个后移，留出空位
while (j>=gap&&nums[j-gap]>temp){//nums[j-gap]元素如果大于temp 那么我们就把nums[j-gap]往后移
nums[j]=nums[j-gap];
j-=gap;
}
nums[j]=temp;
}
}
public static void shellSort(long[] nums){
int gap=nums.length/2;
while (gap!=1){
insertSortWithGap(nums,gap);
gap/=2;
}
insertSortWithGap(nums,1);//在gap为1时1再插入排序 数组一定有序
}
为什么希尔排序至少包含一次直接插入排序，但是性能比直接插入还更好？
我们来试图构建这样一个数学模型:
假设数组中有n个元素 每个元素都和它后边地元素对应一种大小关系 此时一共会有（n-1）+（n-2）+。。。。。+1种关系
现在有一个桶 如果 前<=后 我们就构建一颗篮球入桶
如果 前>后 我们就构建一颗红球入桶
我们排序的目的就是把红球涂成篮球 消除 前>后 这种情况
为什么冒泡和插入慢 因为这两种排序都是相邻两两比较 一次只能把一颗红球涂成篮球 而希尔排序由于存在分组 它可以在预处理的时候就让元素更接近它排序后的位置，也就是一次把多个红球涂成篮球 所以它的性能是要优于冒泡和直接插排的
总结：希尔排序的时间复杂度是O(N^1.3)(看别人写的，自己也不会证明。。。) 空间复杂度明显是O（1） 由于涉及到分组，相同元素可能被分在不同组里，所以丧失了稳定性
四、选择排序
“选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。”
通俗的说 我们在无序区间选择最小的数交换到无需区间第一个数 以此类推即可
选择排序代码详解：
public static void selectSort(long[] nums){
//有序区间[0,i) 无序区间[i,nums.length)
for (int i=0;i<nums.length;i++){
//我们每一次选择无序区间的最小值交换到i位置即可
int minIndex=i;
for (int j=i+1;j<nums.length;j++){
if (nums[j]<nums[minIndex]){
minIndex=j;
}
}
swap(nums,minIndex,i);
}
}
总结：选择排序的时间复杂度明显是O(N^2) 空间复杂度是O(1) 这里重点说明选择排序的稳定性分析
**如图所示 我们每次从无序区间内选择最小的数和无序区间第一个数交换 此时无序区间最小的值是4 那么他就应该和8交换 而这两个8的位置就互换了 因此选择排序不具有稳定性 **
五、堆排序
“堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。”
堆排序的本质也是一种选择排序 利用堆结构找出最大值交换到无需区间后边
如果有同学对堆结构还不太了解可以看我上一篇对堆结构的分析
堆排序可以分为以下两个步骤
1、对整个数组建堆
2、交换堆顶元素和无序区间最后一个元素
此时无序区间和堆里都少了一个元素
我们对堆的【0】向下调整以满足堆结构
不断循环（n-1）次找出最值并交换
堆排序详解代码：
public static void heapSort(long[] nums){
//建立大堆
creatBigHeap(nums);
for (int i=0;i<nums.length-1;i++){
//交换之前的无序区间[0,num.length-i)
swap(nums,0,nums.length-1-i);
//交换之后的无序区间[0,num.length-i-1)
justDown(nums,nums.length-i-1,0);
}
}
private static void creatBigHeap(long[] nums) {
for (int i=(nums.length-2)/2;i>=0;i--){
justDown(nums,nums.length,i);
}
}
private static void justDown(long[] nums, int size, int index) {
int left=index*2+1;
while (left<size){
int largest=(left+1<size&&nums[left+1]>nums[left])?left+1:left;
largest=nums[largest]>nums[index]?largest:index;
if (largest==index) return;
swap(nums,index,largest);
index=largest;
left=index*2+1;
}
}
*总结：堆排序本质上也是一种选择排序 不过由于堆这种特殊的结构导致它找出最值并维持下一个最值的复杂度是O(logN) 而我们需要找n-1个最值 因此堆排序的时间复杂度是O(NlogN) 堆排序并没有最好最坏情况 它的空间复杂度明显是O(1) **
由于堆排序有向下调整的过程存在交换，所以后面的3b反而到了堆顶，因此堆排序不具有稳定性
好啦，今天的 排序分享到这里，由于博主自身水平有限，文中不乏一些错误，欢迎提出 一起进步！如果觉得对你有用请一键三连！
版权归原作者 yan扬 所有， 如有侵权，请联系我们删除。