共计 8282 个字符，预计需要花费 21 分钟才能阅读完成。
排序算法
排序算法算是咱们学习算法的入门篇，在正式介绍各种排序算法前，先介绍一下要用到的一些术语：
- 稳固排序：如果 a 原本在 b 的后面，且 a ==b，排序当前 a 仍旧在 b 的后面，那就是稳固排序，否在是非稳固排序
- 原地排序：就是在排序过程中不申请多于的存储空间，只利用原来存储待排数据的存储空间进行比拟和替换的数据排序。而非原地排序就是须要利用额定的数组来辅助排序。
总览：
抉择排序
代码思路
首先找到数组中最小的元素，其次将其与数组中第一个元素替换地位，而后在剩下的数组中找到最小的元素，而后和第二个元素替换，以此类推，直到替换结束。
特点
数据挪动起码，运行工夫与数据输出时的程序无关
复杂度与排序特点
- 工夫复杂度：O(n²)
- 空间复杂度：O(1)
- 非稳固排序
- 原地排序
应用环境
数据量少
算法代码
// 从小到大
private static void sort(int[] nums){
int n=nums.length;
int minIndex,temp;
for(int i=0;i<n-1;i++){
minIndex=i;
for(int j=i+1;j<n;j++){if(nums[j]<nums[minIndex]){minIndex=j;}
}
temp=nums[i];
nums[i]=nums[minIndex];
nums[minIndex]=temp;
}
}插入排序
代码思路
像抓牌一样，将牌临时放入当初的适当的地位。当到最初一个元素时就排序实现了。就像把一个无序数组中的数据整合到一个有序数组中。
特点
运行工夫与输出状况无关，对于一个局部有序（数组中元素离最终地位都不远，或者一个有序的大数组加一个小数组）来说速度比拟快
复杂度
- 工夫复杂度：O(n²)
- 空间复杂度：O(1)
- 稳固排序
- 原地排序
应用环境
数组根本有序，或者一个有序的大数组中增加一些小数据。
算法代码
// 从小到大排序
private static void sort(int[] nums) {
int n=nums.length;
int preIndex,current;
for(int i=1;i<n;i++){
preIndex=i-1;
current=nums[i];
while (preIndex>=0&&nums[preIndex]>current){nums[preIndex+1]=nums[preIndex];
preIndex--;
}
nums[preIndex+1]=current;
}
}冒泡排序
代码思路
非常简略，反复拜访，顺次比拟进行替换，替换过多
- 比拟相邻元素，大就替换
- 从第一对开始，到最初一对，一次排序后保障最大的位于开端
- 反复 n 次
特点
思路简略
复杂度
- 工夫复杂度：O(n2)
- 空间复杂度：O(1)
- 稳固排序
- 原地排序
应用环境
无实用场景个别用于学习算法。
算法代码
private static void sort(int[] nums) {
int n=nums.length;
for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(nums[j]>nums[j+1]){int temp=nums[j];
nums[j]=nums[j+1];
nums[j+1]=temp;
}
}
}
}改进冒泡排序算法
在咱们遍历的过程中，会发现从开始第一队到最初一对都没有产生替换，此时意味着，剩下这些待排序的元素曾经是有序的数据，无序再次排序，所以咱们能够引入一个标记，当遇到此状况的时候，间接跳出循环。缩小无意义的比拟和缩短排序工夫。
希尔排序（放大增量排序）
代码思路
希尔排序是插入排序的一种变种，原来插入排序的劣势在于数据根本有序的状况下性能很好，然而如果原数组中的元素间隔其正确地位很远的话，效率就不是很高，而希尔排序正是优化了这一点。
希尔排序就是为了加快速度简略的改良了插入排序，替换不相邻的元素以对数据的部分进行排序。
先使数组中任意距离为 h 的元素是有序的。最初对于一个以 1 结尾的的 h 序列咱们都可能将其排序。
具体步骤：
- 先将整个待排序的记录序列分隔成若干子序列，别离进行间接插入排序
-
- 抉择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，依据对应的增量 ti，将待排序列宰割成若干长度为 m 的子序列，别离对各子表进行间接插入排序。仅增量因子为 1 时，整个序列作为一个表来解决，表长度即为整个序列的长度。
特点
基于插入排序的疾速排序
复杂度
- 工夫复杂度：O(nlogn)
- 空间复杂度：O(1)
- 非稳固排序
- 原地排序
应用环境
大型数组，大多数状况下希尔排序都是比拟高效且简略的算法
算法代码
private static void sort(int[] nums) {
int n=nums.length;
int gap=n/2;
while (gap>0){for(int j=gap;j<n;j++){
int i=j;
while ((i>=gap&&nums[i-gap]>nums[i])){int temp=nums[i];
nums[i]=nums[i-gap];
nums[i-gap]=temp;
i-=gap;
}
}
gap=gap/2;
}
}须要留神的是，对各个分组进行插入的时候并不是先对一个组排序完了再对另一个组排序，而是轮流对每个组进行排序。
归并排序
代码思路
将一个大的无序数组有序，咱们能够利用归并的思维来进行排序，行将大问题化为小问题进行解决。
- 把长度为 n 的输出序列分成两个长度为 n / 2 的子序列；
- 对这两个子序列别离采纳归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
特点
速度较快，不受输出数据的影响，所需额定空间与 N 成正比
复杂度
- 工夫复杂度：O(nlogn)
- 空间复杂度：O(n)
- 稳固排序
- 非原地排序
应用环境
算法代码
private static void sort(int[] nums,int start,int end) {
// 如果 left==right，表明数组中只有一个元素，则不必递归排序
if(start<end){
// 将大数组宰割成两个小数组
int mid=(start+end)/2;
// 别离排序
sort(nums,start,mid);
sort(nums,mid+1,end);
// 进行合并
merge(nums,start,mid,end);
}
}
// 合并函数，把两个有序的数组合并起来
private static void merge(int[] nums,int left,int mid,int right){int []tmp=new int[nums.length];
int p1=left,p2=mid+1,k=0;
while (p1<=mid && p2<=right){if(nums[p1]<=nums[p2])
tmp[k++]=nums[p1++];
else
tmp[k++]=nums[p2++];
}
while (p1<=mid)
tmp[k++]=nums[p1++];
while (p2<=right)
tmp[k++]=nums[p2++];
// 把数组复制到原数组中
for (int i=left;i<=right;i++)
nums[i]=tmp[i];
}快排（三取样切分）
代码思路
咱们从数组中抉择一个元素，咱们把这个元素称之为中轴元素吧，而后把数组中所有小于中轴元素的元素放在其右边，所有大于或等于中轴元素的元素放在其左边，显然，此时中轴元素所处的地位的是有序的。也就是说，咱们无需再挪动中轴元素的地位。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不蕴含中轴元素)，接着咱们通过递归的形式，让中轴元素右边的数组和左边的数组也反复同样的操作，直到数组的大小为 1，此时每个元素都处于有序的地位。
特点
利用宽泛，原地排序，简直不须要额定的空间
复杂度
- 工夫复杂度：O(nlogn)
- 空间复杂度：O(logn)
- 非稳固排序
- 原地排序
应用环境
宽泛
算法代码
private static void sort(int[] nums,int start,int end) {if(nums.length<0)
return;
if(start>=end)
return;
int left=start;
int right=end;
int temp=nums[left];
while (left<right){while (left<right && nums[right]>=temp)
right--;
nums[left]=nums[right];
while (left<right && nums[left]<=temp)
left++;
nums[right]=nums[left];
}
nums[left]=temp;
sort(nums,start,left-1);
sort(nums,left+1,end);
}堆排序
代码思路
利用堆这种数据结构，沉积是一个近似齐全二叉树的构造，并同时满足沉积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 将初始待排序关键字序列 (R1,R2….Rn) 构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素 R[1]与最初一个元素 R[n]替换，此时失去新的无序区 (R1,R2,……Rn-1) 和新的有序区(Rn), 且满足 R[1,2…n-1]<=R[n]；
- 因为替换后新的堆顶 R[1]可能违反堆的性质，因而须要对以后无序区 (R1,R2,……Rn-1) 调整为新堆，而后再次将 R[1]与无序区最初一个元素替换，失去新的无序区 (R1,R2….Rn-2) 和新的有序区(Rn-1,Rn)。一直反复此过程直到有序区的元素个数为 n -1，则整个排序过程实现。
复杂度
- 工夫复杂度：O(nlogn)
- 空间复杂度：O(1)
- 非稳固排序
- 原地排序
算法代码
public static void sort(int[] list) {
// 结构初始堆, 从第一个非叶子节点开始调整, 左右孩子节点中较大的替换到父节点中
for (int i = (list.length) / 2 - 1; i >= 0; i--) {headAdjust(list, list.length, i);
}
// 排序，将最大的节点放在堆尾，而后从根节点从新调整
for (int i = list.length - 1; i >= 1; i--) {int temp = list[0];
list[0] = list[i];
list[i] = temp;
headAdjust(list, i, 0);
}
}
private static void headAdjust(int[] list, int len, int i) {int k = i, temp = list[i], index = 2 * k + 1;
while (index < len) {if (index + 1 < len) {if (list[index] < list[index + 1]) {index = index + 1;}
}
if (list[index] > temp) {list[k] = list[index];
k = index;
index = 2 * k + 1;
} else {break;}
}
list[k] = temp;
}计数排序
代码思路
计数排序是一种适宜于最大值和最小值的差值不是不是很大的排序。
根本思维：就是把数组元素作为数组的下标，而后用一个长期数组统计该元素呈现的次数，例如 temp[i] = m, 示意元素 i 一共呈现了 m 次。最初再把长期数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
复杂度
- 工夫复杂度：O(n+k)
- 空间复杂度：O(n+k)
- 稳固排序
- 非原地排序
应用环境
其排序速度快于任何比拟排序算法。当 k 不是很大并且序列比拟集中时，计数排序是一个很无效的排序算法。
算法代码
public static void sortCount(int[] arr, int min, int max) {
int len = arr.length;
int[] tem = new int[max - min + 1];
for(int i = 0; i < len; i++) {tem[arr[i] - min] += 1;
}
for(int i = 0, index = 0; i < tem.length; i++) {int item = tem[i];
while(item-- != 0) {arr[index++] = i + min;
}
}
}桶排序
代码思路
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的要害就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假如输出数据遵从均匀分布，将数据分到无限数量的桶里，每个桶再别离排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排）。
- 设置一个定量的数组当作空桶；
- 遍历输出数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
复杂度
- 桶排序最好状况下应用线性工夫 O(n)，桶排序的工夫复杂度，取决与对各个桶之间数据进行排序的工夫复杂度，因为其它局部的工夫复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的工夫也会越少。但相应的空间耗费就会增大
- 工夫复杂度：O(n+k)
- 空间复杂度：O(n+k)
- 稳固排序
- 非原地排序
算法代码
public static void main(String[] args) {// 输出元素均在 [0, 10) 这个区间内
float[] arr = new float[] {0.12f, 2.6f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(float[] arr) {
// 新建一个桶的汇合
ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>();
for (int i = 0; i < 10; i++) {
// 新建一个桶，并将其增加到桶的汇合中去。// 因为桶内元素会频繁的插入，所以抉择 LinkedList 作为桶的数据结构
buckets.add(new LinkedList<Float>());
}
// 将输出数据全副放入桶中并实现排序
for (float data : arr) {int index = getBucketIndex(data);
insertSort(buckets.get(index), data);
}
// 将桶中元素全副取出来并放入 arr 中输入
int index = 0;
for (LinkedList<Float> bucket : buckets) {for (Float data : bucket) {arr[index++] = data;
}
}
}
/**
* 计算失去输出元素应该放到哪个桶内
*/
public static int getBucketIndex(float data) {
// 这里例子写的比较简单，仅应用浮点数的整数局部作为其桶的索引值
// 理论开发中须要依据场景具体设计
return (int) data;
}
/**
* 咱们抉择插入排序作为桶内元素排序的办法 每当有一个新元素到来时，咱们都调用该办法将其插入到失当的地位
*/
public static void insertSort(List<Float> bucket, float data) {ListIterator<Float> it = bucket.listIterator();
boolean insertFlag = true;
while (it.hasNext()) {if (data <= it.next()) {it.previous(); // 把迭代器的地位偏移回上一个地位
it.add(data); // 把数据插入到迭代器的以后地位
insertFlag = false;
break;
}
}
if (insertFlag) {bucket.add(data); // 否则把数据插入到链表末端
}
}
基数排序
代码思路
基数排序是依照低位先排序，而后收集；再依照高位排序，而后再收集；顺次类推，直到最高位。有时候有些属性是有优先级程序的，先按低优先级排序，再按高优先级排序。最初的秩序就是高优先级高的在前，高优先级雷同的低优先级高的在前。
- 获得数组中的最大数，并获得位数；
- arr 为原始数组，从最低位开始取每个位组成 radix 数组；
- 对 radix 进行计数排序（利用计数排序实用于小范畴数的特点）；
特点
针对计数排序进行优化的一种算法。
复杂度
- 工夫复杂度：O(kn)
- 空间复杂度：O(n+k)
- 稳固排序
- 非原地排序
算法代码
public static void main(String[] args) {int[] arr = new int[] { 5,789,2138,456,3,1,9,1,13,4984,3};
radixSort(arr,10000);
System.out.println(Arrays.toString(arr));
}
private static void radixSort(int[] array,int d)
{
int n=1;// 代表位数对应的数：1,10,100...
int k=0;// 保留每一位排序后的后果用于下一位的排序输出
int length=array.length;
int[][] bucket=new int[10][length];// 排序桶用于保留每次排序后的后果，这一位上排序后果雷同的数字放在同一个桶里
int[] order=new int[length];// 用于保留每个桶里有多少个数字
while(n<d)
{for(int num:array) // 将数组 array 里的每个数字放在相应的桶里
{int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)// 将前一个循环生成的桶里的数据笼罩到原数组中用于保留这一位的排序后果
{if(order[i]!=0)// 这个桶里有数据，从上到下遍历这个桶并将数据保留到原数组中
{for(int j=0;j<order[i];j++)
{array[k]=bucket[i][j];
k++;
}
}
order[i]=0;// 将桶里计数器置 0，用于下一次位排序
}
n*=10;
k=0;// 将 k 置 0，用于下一轮保留位排序后果
}
}
睡眠排序
代码思路
代码思路倒是很简略，就是利用线程睡眠来进行排序，让线程睡眠、
特点
娱乐算法，没啥特点就是好玩
算法代码
public static void sleepSort(int[] array) {for (int i : array) {new Thread(()->{
try {Thread.sleep(i);
} catch (Exception e) {e.printStackTrace();
}
System.out.println(i);
}).start();}
}
public static void main(String[] args) {int[] array = {10, 30, 50, 60, 100, 40, 150, 200, 70};
sleepSort(array);
}
随机排序排序
代码思路
就是让零碎随机排序，而后验证是否有序
特点
巨简单，看命
算法代码
public static void randSortX(int [] array){List<Integer> list=new ArrayList<>();
for (Integer integer : array) {list.add(integer);
}
int pre=0;
int index=0;
while(true){
pre=0;
for (index = 1; index < list.size(); index++) {if(list.get(index)>list.get(pre)){pre++;}else{break;}
}
if(pre+1==list.size()){break;}
Collections.shuffle(list);
}
System.out.println(list.toString());
}
public static void main(String[] args) {int[] array = {10, 30, 50, 60, 100, 40, 150, 200, 70};
randSortX(array);
}最初
- 如果感觉看完有播种，心愿能给我点个赞，这将会是我更新的最大能源，感激各位的反对
- 欢送各位关注我的公众号【java 冢狐】，专一于 java 和计算机基础知识，保障让你看完有所播种，不信你打我
- 如果看完有不同的意见或者倡议，欢送多多评论一起交换。感激各位的反对以及厚爱。
——我是冢狐，和你一样酷爱编程。
正文完
