一、排序的概述
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
八大排序都属于内部排序，也就是只考虑数据量较小仅需要使用内存的排序算法，他们之间关系如下：
什么是排序的稳定性?
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持
不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳
定的；否则称为不稳定的。
该排序即为不稳定的排序，因为相同的4在排序之后顺序变了。
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
说的通俗一点就是每次默认前面的元素是有序的，然后用该位置的元素就寻找合适位置插入。
那插入排序的时间复杂度是多少吗?
因为每一位都需要和前面有序数组的每一位去比较所以时间复杂度为o(n).
最好情况下，当数组有序时，每个数字只需要比较一次，最优时间复杂度为o(1).
/**
* 插入排序
* 时间复杂度 : o(n²)
* 最好情况下 有序 时间复杂度 o(n)
* 空间复杂度: o(1)
* 稳定性: 稳定
* 一个本身就稳定的排序可以实现为不稳定的排序
* 一个本身就不稳定的排序能变成稳定的排序吗？
* @param arr
*/
public static void insertsort(int[] arr) {
//插入排序
for (int i = 1; i < arr.length; i ) {
int j = i - 1;
int tmp = arr[i];
while(j >= 0) {
if(arr[j] > tmp) {
arr[j 1] = arr[j];
} else {
break;
}
j--;
}
arr[j 1] = tmp;
}
}
希尔排序按其设计者希尔（donald shell）的名字命名，该算法由希尔在 1959 年所发表的论文“a high-speed sorting procedure” 中所描述。
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
希尔排序主要是对插入排序进行了优化，因为当数组为逆序时，插入排序会变得十分的慢，希尔排序在最后一次插入排序之前进行了预排序。
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
/**
* 希尔排序
* o(n^1.3次方)
* @param
*/
public static void shellsort(int[] arr) {
//希尔排序
int gap = arr.length;
while(gap > 1) {
gap /= 2;
shell(arr,gap);
}
}
public static void shell(int[] arr,int gap) {
for (int i = gap; i < arr.length; i ) {
int tmp = arr[i];
int j = i - gap;
for (; j >= 0; j-=gap) {
if(arr[j] > tmp) {
arr[j gap] = arr[j];
}else {
break;
}
}
arr[j gap] = tmp;
}
}
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
选择排序的思想特别简单，就是每一趟确定一个最大值或者最小值，数组遍历完成后数组也就有序了。
1.在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
2.若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3.在剩余的array[i]–array[n-2]（array[i 1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
/**
* 选择排序
* 时间复杂度: o(n²)
* 与数组是否有序无关
* 空间复杂度: o(1)
* 稳定性: 不稳定
* @param
*/
public static void selectsort(int[] arr) {
for (int i = 0; i < arr.length; i ) {
int minindex = i;
for (int j = i 1; j < arr.length; j ) {
if(arr[j] < arr[minindex]) {
minindex = j;
}
}
if(minindex != i) {
int h = arr[i];
arr[i] = arr[minindex];
arr[minindex] = h;
}
}
}
选择排序实现起来比较简单，但时间复杂度相对比较高达到了o(n)，我们能不能对此进行优化一下。
我们遍历一趟数组，找到一个最大值的下标和最小值的下标，一趟下来就直接确定了最大值和最小值，这样就能优化一点。
public static void selectsort2(int[] arr){
int left = 0;
int right = arr.length - 1;
while(left < right) {
int minindex = left;
int maxindex = left;
for (int i = left 1; i <= right; i ) {
if(arr[i] < arr[minindex]) {
minindex = i;
}
if(arr[i] > arr[maxindex]) {
maxindex = i;
}
}
swap(arr,left,minindex);
//如果maxindex == left证明已经把最大值放到了minindex位置
if(maxindex == left) {
maxindex = minindex;
}
swap(arr,right,maxindex);
left ;
right--;
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
我们发现当数组首位置的元素就是最大值时，我们可以发现在进行最小值交换后，最大值的数被换到了minindex位置，所以我们要进行那样的判断。
堆排序(heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆
来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
大概的流程就是如果需要排一个升序数组，那么就建一个大根堆，然后每次将堆顶元素和最后一个位置的元素交换，然后在将堆顶元素进行向下操作。这样我们就能每次选择一个数组最大值放到尾部。
/**
* 堆排序
* 时间复杂度 : o(n * logn)
* 空间复杂度: o(1)
* @param
*/
public static void heapsort(int[] arr) {
createbigheap(arr);
int end = arr.length - 1;
while(end > 0) {
swap(arr,0,end);
shiftdown(arr,0,end);
end--;
}
}
public static void createbigheap(int[] arr) {
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
shiftdown(arr,i,arr.length);
}
}
public static void shiftdown(int[] arr,int parent,int len) {
int child = parent * 2 1;
while (child < len) {
if(child 1 < len && arr[child 1] > arr[child]) {
child ;
}
if(arr[child] > arr[parent]) {
swap(arr,child,parent);
} else {
break;
}
parent = child;
child = parent * 2 1;
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：o(n*logn)
3. 空间复杂度：o(1)
4. 稳定性：不稳定
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特
点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
我们可以发现每进行一次排序就能确定一个最大值出来，n个数需要进行n-1趟冒泡。
/**
* 冒泡排序
* 时间复杂度 o(n²)
* 空间复杂度 o(1)
* 稳定的排序
* @param
*/
public static void bubblesort(int[] arr) {
for (int i = 0; i < arr.length - 1; i ) {
boolean flg = false;
for (int j = 0; j < arr.length - i - 1; j ) {
if(arr[j] > arr[j 1]) {
flg = true;
swap(arr,j,j 1);
}
}
if(flg == false) {
break;
}
}
}
public static void swap(int[] arr,int l,int r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：o(n^2)
3. 空间复杂度：o(1)
4. 稳定性：稳定
快速排序是hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
public static void quicksort(int[] arr) {
quick(arr,0,arr.length - 1);
}
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot 1,end);
}
我们每次主要要去写找基准的方法，这里我们一共有三种找基准的方法。
将区间按照基准值划分为左右两半部分的常见方式有：
hoare版
public static int partition(int[] arr,int left,int right) {
//hoare法
int i = left;
int pivot = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivot) {
right--;
}
while (left < right && arr[left] <= pivot) {
left ;
}
swap(arr,left,right);
}
swap(arr,i,left);
return left;
}
挖坑法
public static int partition1(int[] arr,int left,int right) {
//挖坑法
int i = left;
int j = right;
int pivot = arr[left];
while(i < j) {
while(i < j && arr[j] >= pivot) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i ;
}
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
前后指针
public static int partition2(int[] arr,int left,int right) {
//前后指针法
int prev = left;
int cur = left 1;
int pivot = arr[left];
while(cur <= right) {
if(arr[cur] < pivot && arr[ prev] != arr[cur]) {
swap(arr,prev,cur);
}
cur ;
}
swap(arr,left,prev);
return prev;
}
快速排序问题解答
为什么要先移动右边？
答案：为了保证当left和right相遇时，left指向的元素是小于pivot的。大家可以手动的画图理解一下。
为什么要包含等号?
为了避免这个情况的出现，排序陷入死循环。
时间复杂度分析
这是快速排序的理想状态下，那当不理想呢?
当数组有序时,时间复杂度达到了o(n²)，空间复杂度达到了o(n),那如何优化呢？
快速排序的优化
三数取中法
每次基准值，在数组首元素，中间值，和末尾值取一个中位数。
这些就可以避免数组有序时造成o(n²)的情况
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
//在进行partition尽量去解决不均匀问题
int mid = findmidvalueofindex(arr,start,end);
swap(arr,mid,start);
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot 1,end);
}
public static int findmidvalueofindex(int[] arr,int start,int end) {
int mid = (end start) / 2;
if(arr[start] < arr[end]) {
if(arr[mid] < arr[start]) {
return start;
}else if(arr[mid] > arr[end]) {
return end;
}else {
return mid;
}
}else {
if(arr[mid] < arr[end]) {
return end;
}else if(arr[mid] > arr[start]) {
return start;
}else {
return mid;
}`在这里插入代码片`
}
}
嵌套插入排序
当快速排序在最后几层时，数组已经趋于有序，在进行快速排序进行递归次数过多，这是我们可以进行插入排序。
public static void quick(int[] arr,int start,int end) {
if(start >= end) {
return;
}
//当数组快趋于有序时，进行插入排序
if((end - start 1) <= 15) {
insert(arr,start,end);
}
//在进行partition尽量去解决不均匀问题
int mid = findmidvalueofindex(arr,start,end);
swap(arr,mid,start);
int pivot = partition2(arr,start,end);
quick(arr,start,pivot - 1);
quick(arr,pivot 1,end);
}
public static void insert(int[] arr,int left,int right) {
for (int i = left 1; i <= right; i ) {
int j = i 1;
for (; j >= 0; j--) {
if(arr[j] > arr[i]) {
arr[j 1] = arr[j];
}else {
break;
}
}
arr[j 1] = arr[i];
}
}
非递归实现
public static void quicksort1(int[] arr) {
stack stack = new stack<>();
int left = 0;
int right = arr.length - 1;
int pivot = partition(arr,left,right);
//判断左边是不是有两个元素
if(left < pivot - 1) {
stack.push(left);
stack.push(pivot - 1);
}
//判断右边是否有两个元素
if(right > pivot 1) {
stack.push(pivot 1);
stack.push(right);
}
while (!stack.isempty()) {
right = stack.pop();
left = stack.pop();
pivot = partition(arr,left,right);
//判断左边是不是有两个元素
if(left < pivot - 1) {
stack.push(left);
stack.push(pivot - 1);
}
//判断右边是否有两个元素
if(right > pivot 1) {
stack.push(pivot 1);
stack.push(right);
}
}
}
快速排序总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：o(n*logn)
- 空间复杂度：o(logn)
- 稳定性：不稳定
归并排序（merge-sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（divide and conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
/**
* 归并排序
* 时间复杂度: o(n*logn)
* 空间复杂度: o(n) //因为创建了临时数组
* 稳定性: 稳定
* @param
*/
public static void mergesort(int[] arr) {
mergesortchild(arr,0,arr.length - 1);
}
public static void mergesortchild(int[] arr,int left,int right) {
if(left >= right) {
return;
}
int mid = (left right) / 2;
mergesortchild(arr,left,mid);
mergesortchild(arr,mid 1,right);
//合并
merge(arr,left,mid,right);
}
public static void merge(int[] arr,int left,int mid,int right) {
int[] array = new int[right - left 1];
int l = left;
int l1 = mid;
int r = mid 1;
int r1 = right;
int k = 0;
while(l <= l1 && r <= r1) {
if(arr[l] < arr[r]) {
array[k ] = arr[l ];
} else {
array[k ] = arr[r ];
}
}
while(l <= l1) {
array[k ] = arr[l ];
}
while(r <= r1){
array[k ] = arr[r ];
}
//保证left到right之间的数据是有序的
for (int i = 0; i < array.length; i ) {
arr[left i] = array[i];
}
}
非递归实现
//非递归实现归并排序
public static void mergesort1(int[] arr) {
int gap = 1;
while(gap < arr.length) {
for (int i = 0; i < arr.length; i =gap*2) {
int left = i;
int mid = left gap - 1;
if(mid >= arr.length) {
mid = arr.length - 1;
}
int right = mid gap;
if(right >= arr.length) {
right = arr.length - 1;
}
merge(arr,left,mid,right);
}
gap *= 2;
}
}
海量数据排序
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1g，需要排序的数据有 100g
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 m
- 分别对 512 m 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
前面我们介绍的七种排序都是基于比较的排序，现在我们来了解几种不用比较的排序
空间换取时间，入的次数和出的次数取决于数据里面的最大值
public class radixsort implements iarraysort {
@override
public int[] sort(int[] sourcearray) throws exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = arrays.copyof(sourcearray, sourcearray.length);
int maxdigit = getmaxdigit(arr);
return radixsort(arr, maxdigit);
}
/**
* 获取最高位数
*/
private int getmaxdigit(int[] arr) {
int maxvalue = getmaxvalue(arr);
return getnumlenght(maxvalue);
}
private int getmaxvalue(int[] arr) {
int maxvalue = arr[0];
for (int value : arr) {
if (maxvalue < value) {
maxvalue = value;
}
}
return maxvalue;
}
protected int getnumlenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght ;
}
return lenght;
}
private int[] radixsort(int[] arr, int maxdigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxdigit; i , dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j ) {
int bucket = ((arr[j] % mod) / dev) mod;
counter[bucket] = arrayappend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos ] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private int[] arrayappend(int[] arr, int value) {
arr = arrays.copyof(arr, arr.length 1);
arr[arr.length - 1] = value;
return arr;
}
}
比较排序中是稳定排序的有: 插入排序，冒泡排序，归并排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
/**
* 计数排序
* 适合数值范围小的数组
* 时间复杂度为o(n 数值范围)
* 空间复杂度: o(范围)
* @param arr
*/
public static void countsort(int[] arr) {
int min = arr[0];
int max = arr[0];
//遍历数组 找最大值 最小值
for (int i = 0; i < arr.length; i ) {
if(arr[i] < min) {
min = arr[i];
}
if(arr[i] > max) {
max = arr[i];
}
}
//开辟一个计数数组，数组大小为数组值的取值范围
int[] ret = new int[max - min 1];
//统计每个数字出现的次数
for (int i = 0; i < arr.length; i ) {
ret[arr[i] - min] ;
}
int k = 0;
for (int i = 0; i < ret.length; i ) {
while(ret[i] > 0) {
arr[k ] = i min;
ret[i]--;
}
}
}
时间复杂度:
时间复杂度为o(n 数值范围)
计数排序适用于数值范围较小的数组
桶排序（bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（θ(n)）。但桶排序并不是比较排序，他不受到o(n log n)下限的影响。
public static void bucketsort(int[] arr) {
arraylist bucket[] = new arraylist[6];// 声明六个桶
for (int i = 0; i < bucket.length; i ) {
bucket[i] = new arraylist();// 确定桶的格式为arraylist
}
for (int i = 0; i < arr.length; i ) {
int index = arr[i] / 10;// 确定元素存放的桶号
bucket[index].add(arr[i]);// 将元素存入对应的桶中
}
for (int i = 0; i < bucket.length; i ) {
bucket[i].sort(null);// 对每一个桶排序，默认排序方式
for (int i1 = 0; i1 < bucket[i].size(); i1 ) {
// 遍历桶中的元素并输出
system.out.print(bucket[i].get(i1) " ");
}
}
}