排序:排序就是对某项数据按照特定的要求,比如大小或字符长短等按照升序或降序排序。

排序过程中设计稳定性,稳定性指的是若有两个相同的数字,比如1和1。如果排序前1在1的前面,排完序后1还在1
的前面。那么就说这个排序算法是稳定的,相反则说明不稳定。

注意:如果本身就是一个稳定的排序,可以将其变成不稳定排序;如果本身就是不稳定排序,不能变成稳定的排序。

常见的排序方法

上面是基于比较的排序。

下面一个一个的分析

一:直接插入排序

直接插入排序指的是将新的数据插入在已经排好序的序列中。比如我们生活中的玩的斗地主,我们需要将新摸的牌按照大小顺序插入到已经排好的扑克牌中。

例如,将无序的整形数组进行排序:

思路:

1.首先判断数组的长度,长度<=1,直接返回

2.将数组第i(>=1)个下标位置的元素放在temp中

3.将j下标位置的元素与temp比较。当小于时退出循环,执行4;当大于时,将j位置的元素赋给j+1,然后j--,然后重复这一步直到退出循环(退出循环的结果有两种)

4.将temp的位置赋给j+1下标的值
public class Insertsort { public static void insertsort(int[] array){ for (int
i = 1; i < array.length; i++) { int temp = array[i]; int j = i-1; for (; j >=0
; j--) { if(array[j]<temp){ break; }else{ array[j+1] = array[j]; } } array[j+1]
= temp; } } public static void main(String[] args) { int[] array = new
int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); insertsort(array); System.out.println("排序后"+
Arrays.toString(array)); } }

直接插入排序总结:

1.直接插入排序的时间复杂度:O(N^2)(将逆序的数据排成顺序)、O(N)(数据本身就是有序的)

2.直接插入排序的空间复杂度O(1)

3.直接插入排序适用于数据量小且数据本身趋于有序的情况

4.直接插入排序是一种稳定排序算法 

二:希尔排序

希尔排序又叫做缩小增量排序,他是直接排序的一种优化。

它的优化逻辑是将一组无序的序列分成若干组gap,然后将每组进行直接插入排序。最终将gap等于1时所得到的序列再进行一次直接插入排序
。gap>1时的排序称为预排序,它的作用是每次直接插入排序完后的序列都更趋近于有序,让整个排序的时间减少。

我们知道直接插入排序的最坏时间复杂度为O(N^2),N是序列中元素的个数。现在假设有10000个无序的数据,如果直接插入排序,所需时间为100,000,000。现在将这些数据分成100组,每组100个数据,每组如果采用直接插入排序,需要时间为10000,那么100组所需时间就为1,000,000。所花时间整整降低了100倍。

希尔排序就是用到的上面的逻辑。

例如,将无序的整形数组进行排序:

思路参照下面图片

public class Shellsort { public static void shell(int[] array,int gap){ for
(int i = gap; i < array.length; i++) { int temp = array[i]; int j = i-gap; for
(; j >=0 ; j-=gap) { if(array[j]<temp){ break; }else{ array[j+gap] = array[j];
} } array[j+gap] = temp; } } public static void shellsort(int[] array){ int gap
= array.length; while(gap>1){ shell(array,gap); gap/=2; } shell(array,1); }
public static void main(String[] args) { int[] array = new
int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); System.out.println("排序后"+ Arrays.toString(array)); } }
 

再来比较一下希尔排序所需时间和直接排序所需时间的比对 
public class Insertsort { public static void insertsort(int[] array){ for (int
i = 1; i < array.length; i++) { int temp = array[i]; int j = i-1; for (; j >=0
; j--) { if(array[j]<temp){ break; }else{ array[j+1] = array[j]; } } array[j+1]
= temp; } } public static void main(String[] args) { int[] array = new
int[100000]; Random random = new Random(); for (int i = 0; i < array.length;
i++) { array[i] = random.nextInt(100000); } long startime =
System.currentTimeMillis(); insertsort(array); long endtime =
System.currentTimeMillis();
System.out.println("直接插入排序算法执行时间"+(endtime-startime)); } }

public class Shellsort { public static void shell(int[] array,int gap){ for
(int i = gap; i < array.length; i++) { int temp = array[i]; int j = i-gap; for
(; j >=0 ; j-=gap) { if(array[j]<temp){ break; }else{ array[i] = array[j]; } }
array[j+gap] = temp; } } public static void shellsort(int[] array){ int gap =
array.length; while(gap>1){ shell(array,gap); gap/=2; } shell(array,1); }
public static void main(String[] args) { int[] array = new int[100000]; Random
random = new Random(); for (int i = 0; i < array.length; i++) { array[i] =
random.nextInt(100000); } long startime = System.currentTimeMillis();
shellsort(array); long endtime = System.currentTimeMillis();
System.out.println("希尔排序算法执行时间"+(endtime-startime)); } }
 

可以看到希尔排序明显快直接排序很多。

希尔排序总结:

1.希尔排序是对直接插入排序的优化

2.希尔排序中gap的取法很多,但是我们一般都取序列长度的一半或者按照质素来取。

3.希尔排序的时间复杂度:O(n^1.25)~O(1.6*n^1.25)

4.希尔排序是不稳定排序 

三:选择排序

选择排序:每次从序列中选出最小(或最大)的一个元素,存放在序列的起始位置;然后再找出序列中次小(或次大)的元素,存放到序列起始的次位置;直到全部待排序的数据 完成排序。

选择排序类似我们生活中的玩扑克牌,一次性排序17张牌。

例如,将无序的整形数组进行排序:

思路:

1.创建一个零时变量minIndex,让minIndex记录i下标

2.遍历数组,找到最小(最大)的一个数的下标j,将minIndex记录为j。如果这个最小的数就是第一个(或最后一个)数,就不动,否者让minIndex下标的数和第一个数交换。

3.i++,重复1~3直到i>array.length
public class Selectsort { 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++) {//内层循环走完以后,minIndex一定最小元素的下标 if (array[minIndex] >
array[j]) minIndex = j; } if (array[i] == array[minIndex]) {//说明i下标这个位置的元素就是最小的
continue; } else { int temp = array[i]; array[i] = array[minIndex];
array[minIndex] = temp; } } } public static void main(String[] args) { int[]
array = new int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); selectSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }

四:堆排序 

堆排序是指利用堆这种数据结构所设计的一种排序算法, 在排序过程中如果想升序,那么就要建大堆;如果想降序就要建小堆。

例如,将无序的整形数组进行排序:
public class heapsort { public static void swap(int[] array,int x,int y){ int
temp = array[x]; array[x] = array[y]; array[y] = temp; } public static void
shiftDown(int[] array,int x,int len){//向下调整 int parent = x; int child =
2*parent+1; while (child<len){
if(child+1<len&&array[child]<array[child+1]){//如果想降序,这里的array[child]>array[child+1]
child++; } if(array[child]>array[parent]){//如果想降序,这里的array[child]<array[parent]
swap(array,child,parent); parent = child; child = 2*parent+1; }else{ break; } }
} public static void creatHeap(int[] array){ for (int parent =
array.length-2>>1; parent >=0 ; parent--) {
shiftDown(array,parent,array.length); } } public static void heapSort(int[]
array){ creatHeap(array);//这里完成堆的创建 int len = array.length-1;//找到最后一个元素的下标
while(len>=0){//这里完成堆的排序 swap(array,0,len); shiftDown(array,0,len); len--; } }
public static void main(String[] args) { int[] array = new
int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); heapSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }

再来看一下选择排序和堆排序排序所花的时间,所给的数据量和插入排序、希尔排序一样。

可以看到选择排序是这四种排序算法中用时最多的,而堆排序是用时最少的。

总结一下选择排序和堆排序的特点:

选择:

1.选择排序的效率很低

2.时间复杂度O(N^2),空间复杂度O(1)

3.不稳定

堆排序

1.效率很高

2.时间复杂度O(N*logN),空间复杂度O(1)

3.不稳定 

五:冒泡排序

冒泡排序是我们接触编程语言最早的一种排序算法,我们大家都很熟悉,这里就不详讲了。

例如,将无序的整形数组进行排序:
public class Bubblesort { public static void bubbleSort(int[] array){ int len
= array.length-1; for (int i = len; i >0 ; i--) { boolean flag = true; for (int
j = 0; j < i; j++) { if(array[j]>array[j+1]){ int temp = array[j]; array[j] =
array[j+1]; array[j+1] = temp; flag = false; } } if(flag)break; } } public
static void main(String[] args) { int[] array = new
int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); bubbleSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }

再来看一下冒泡排序算法所花时间,数据量同前面一样

  

可以看到冒泡排序是目前所有排序算法中用时最多的一种排序算法,所以效率极低。 

冒泡排序的特点总结

1.冒泡排序算法很容易理解和掌握,但是它在处理一组很大无序的数据时效率极低。

2.时间复杂度O(N^2)——将逆序转成顺序,O(1)——本身就有序,空间复杂度O(1)

3.是一种稳定的排序

六:快速排序

 快速排序是一种基于二叉树结构的交换排序方法,其思想是:
任取待排序元素序列中的元素作为基准值,按照该排序码将待排序集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

将区间按照基准值分为左右两半部分的常见方式有:

1.Hoare版

 例如,将无序的整形数组进行排序:

思路:

左边第一个元素做基准值key,右边先走(避免left、right相遇时,该位置的元素大于基准值)

(1)定义left、right并附上相应的下标,以left下标所对应的元素为基准

(2)左边的left向右走,右边的right向左走。left找到比基准值大的停下来,right找到比基准值小的停下来。交换此时left、right下标所对应的元素,交换以后继续找。

(3)当left>=right时,让此时left下标的元素和基准值交换。交换以后,以left下标右边和左边为新的待排序数组继续执行1~3,直到整个数组完成排序。

public class HoareSort { public static void swap(int[] array,int x,int y){ int
temp = array[x]; array[x] = array[y]; array[y] = temp; } public static int
quickSort(int[] array,int left,int right){ int keyIndex = left; int temp =
array[left]; while(left<right){ while(left<right &&
array[right]>=temp){//执行完这个循环出去的一定是小于等于temp的元素 right--; }
while(left<right&&array[left]<=temp){//执行完这个循环出去的一定是大于等于temp的元素 left++; }
swap(array,left,right); } swap(array,keyIndex,left); return left; } public
static void hoareSort(int[] array,int left,int right){ if(left>=right)return;
int pivot = quickSort(array,left,right); hoareSort(array,left,pivot-1);
hoareSort(array,pivot+1,right); } public static void main(String[] args) {
int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); hoareSort(array,0,array.length-1);
System.out.println("排序后"+ Arrays.toString(array)); } }
 再来看一下这六种排序算法测试同一组大数据所花的时间

因为快速排序和堆排序都是基于二叉树结构的排序算法,所以他们所用的时间差不多。

但是注意

Hoare版本的快排如果序列本来就是有序的,那么如果样本数量很大,就会造成栈溢出
int[] array = new int[100000]; Random random = new Random(); for (int i = 0;
i < array.length; i++) { array[i] = random.nextInt(100000); }
hoareSort(array,0,array.length-1);//先让快速排序将无序的序列变成有序 long startime =
System.currentTimeMillis(); hoareSort(array,0,array.length-1);//快速排序排序有序序列 long
endtime = System.currentTimeMillis();
System.out.println("快速排序算法执行时间"+(endtime-startime));
  

2.挖坑法写快速排序

思路:

(1)定义left、right并赋上相应的下标,记录当前left下标所对应的元素为temp

(2)左边的left向右走、右边的right向左走。right先走,right找到比temp小的值停下来,将right所在位置的元素赋给left所在的位置。left找到比temp大的值停下来,将left所在位置的元素赋给right所在的位置。

(3)当left>=right时,将temp的值赋给left所在的位置,返回left 

(4)以left下标右边和左边为新的待排序数组继续执行1~3,直到整个数组完成排序。
class QuickSort{ public static int quickSort2(int[] array, int left, int
right) { int temp = array[left]; while (left < right) { while (left < right &&
array[right] >= temp) {//执行完这个循环出去的一定是小于等于temp的元素 right--; } array[left] =
array[right]; while (left < right && array[left] <= temp)
{//执行完这个循环出去的一定是大于等于temp的元素 left++; } array[right] = array[left]; } array[left]
= temp; return left; } public void digHole(int[] array,int left,int right){
if(left>=right)return; int pivot = quickSort2(array,left,right);
digHole(array,left,pivot-1); digHole(array,pivot+1,right); } } public class
HoareSort { public static void main(String[] args) { QuickSort quickSort = new
QuickSort(); int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
System.out.println("排序前"+ Arrays.toString(array));
quickSort.digHole(array,0,array.length-1); System.out.println("排序后"+
Arrays.toString(array)); } }
3.前后指针法

思路:

(1)记录序列左边第一个数为temp,第二个数为cur

(2)从序列左边第二个数(下表为i)开始,比较它和temp的大小关系,若小于,则让cur下标的数和i下标的数交换,同时cur++;若大于,则让i++。重复执行(2)直到i>right退出循环

(3)让temp与cur-1下标位置的数交换,返回cur-1

(4)以(3)返回的结果分成左右两个子序列,重复1~4直到将序列排成有序

public int quickSort3(int[] array, int left,int right) { int temp =
array[left]; int cur = left + 1; for (int i = left + 1; i <=right; i++) { if
(array[i] < temp) { swap(array, i, cur); cur++; } } swap(array, left, cur - 1);
return cur - 1; } public void pointer(int[] array,int left,int right){
if(left>=right)return; int pivot = quickSort3(array,left,right);
pointer(array,left,pivot-1); pointer(array,pivot+1,right); } } public class
HoareSort { public static void main(String[] args) { QuickSort quickSort = new
QuickSort(); int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
System.out.println("排序前"+ Arrays.toString(array));
quickSort.pointer(array,0,array.length-1); System.out.println("排序后"+
Arrays.toString(array)); } }
快速排序的优化

通过上面的测试我们发现,当给一组有序且很大的数据时,如果用快速排序就会造成栈溢出,溢出的原因就是因为快速排序在递归的时候要开辟内存空间,而递归的次数受树高度的影响。给定一组有序序列,在快排时就等同于只有左树或者只有右树,这样递归的次数就是这个序列的长度,因此给定的序列越大,递归次数越多就会越容易栈溢出。

为了解决上面的问题,主要有以下办法

1.采用混合排序(优化的是区间)——没有根本上解决问题

采用混合排序也就是先采用快排,让递归达到某个深度以后采用其他排序算法,这样就可以在一定程度上减缓栈溢出的概率
class QuickSort{ public static void insertsort(int[] array){ for (int i = 1; i
< array.length; i++) { int temp = array[i]; int j = i-1; for (; j >=0 ; j--) {
if(array[j]<temp){ break; }else{ array[j+1] = array[j]; } } array[j+1] = temp;
} } public static void swap(int[] array, int x, int y) { int temp = array[x];
array[x] = array[y]; array[y] = temp; } public static int quickSort(int[]
array, int left, int right) { int keyIndex = left; int temp = array[left];
while (left < right) { while (left < right && array[right] >= temp)
{//执行完这个循环出去的一定是小于等于temp的元素 right--; } while (left < right && array[left] <=
temp) {//执行完这个循环出去的一定是大于等于temp的元素 left++; } swap(array, left, right); }
swap(array, keyIndex, left); return left; } public static void hoareSort(int[]
array,int left,int right){ if(left>=right)return; // if(right-left+1<70000){ //
insertsort(array); // return; } int pivot = quickSort(array,left,right);
hoareSort(array,left,pivot-1); hoareSort(array,pivot+1,right); } } public class
HoareSort { public static void main(String[] args) { QuickSort quickSort = new
QuickSort(); int[] array = new int[100000]; Random random = new Random(); for
(int i = 0; i < array.length; i++) { array[i] = random.nextInt(100000); }
quickSort.hoareSort(array,0,array.length-1);//让序列变得有序 long startime =
System.currentTimeMillis(); quickSort.hoareSort(array,0,array.length-1); long
endtime = System.currentTimeMillis();
System.out.println("快速排序算法执行时间"+(endtime-startime)); } }
下面是没有优化的效果

然后将代码注释处去掉注释以后

2.采用三数取中法(优化分割区间的方法)——从根本上解决递归深度太深的问题

思路如下

public static int getmidIndex(int[] array,int left,int right){ int mid =
left+((right-left)>>1); if(array[left]<array[right]){
if(array[mid]<array[left]){ return left; }else if(array[mid]>array[right]){
return right; }else{ return mid; } }else{ if(array[mid]<array[right]){ return
right; }else if(array[mid]>array[left]){ return left; }else { return mid; } } }
public static void hoareSort(int[] array,int left,int right){
if(left>=right)return; // if(right-left+1<70000){ // insertsort(array); //
return; // } int index = getmidIndex(array,left,right); swap(array,left,index);
int pivot = quickSort(array,left,right); hoareSort(array,left,pivot-1);
hoareSort(array,pivot+1,right); }
 优化以后的结果

非递归实现快速排序

思路见下图

class QuickSort2{ public static int quickSort(int[] array, int left, int
right) { int temp = array[left]; while (left < right) { while (left < right &&
array[right] >= temp) {//执行完这个循环出去的一定是小于等于temp的元素 right--; } array[left] =
array[right]; while (left < right && array[left] <= temp)
{//执行完这个循环出去的一定是大于等于temp的元素 left++; } array[right] = array[left]; } array[left]
= temp; return left; } public static void hoareSort(int[] array,int left,int
right){ Stack<Integer> stack = new Stack<>(); int pivot =
quickSort(array,left,right); if(pivot>left+1){ stack.push(left);
stack.push(pivot-1); } if(pivot<right-1){ stack.push(pivot+1);
stack.push(right); } while(!stack.isEmpty()){ right = stack.pop(); left =
stack.pop(); pivot = quickSort(array,left,right); if(pivot>left+1){
stack.push(left); stack.push(pivot-1); } if(pivot<right-1){
stack.push(pivot+1); stack.push(right); } } } } public class HoareSort2 {
public static void main(String[] args) { QuickSort2 quickSort = new
QuickSort2(); int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
System.out.println("排序前"+ Arrays.toString(array));
quickSort.hoareSort(array,0,array.length-1); System.out.println("排序后"+
Arrays.toString(array)); } }
 再来看一下非递归快速排序,排序所花时间,数据样本和前面的都一样

将一组有序数据排序

可以看到效率不如优化后的递归排序

将无序数据排成有序

效果也比优化后的递归排序差一点 

快速排序特点总结:

1.时间复杂度O(N*logN)——所有的左右子序列刚好是整体序列的一半时

2.空间复杂度O(logN)——满二叉树的高度

3.不稳定

七.归并排序

归并排序是利用分治算法思想将序列分解成左右两个子序列,让两个子序列有序以后,再将左右子序列合并排序,最终得到一个完全有序的序列。

思路:

一个数组一分为二,两边分别排序,排好序后,创建一个数组,将排好序的数字左右两边比较大小,将小的放在新数组中,遇到某边越界以后,将另一边剩下的数全部拷贝到新数组中,最后将数组拷贝回原来的数组。

具体操作见下图

class Soultion{ public static void merger(int[] array,int left,int mid,int
right){ int s1 = left; int e1 = mid; int s2 = mid+1; int e2 = right; int[]
tempArr = new int[right-left+1]; int k = 0; while(s1<=e1 && s2<=e2){
if(array[s1]<=array[s2]){ tempArr[k++] = array[s1++]; }else{ tempArr[k++] =
array[s2++]; } } while(s1<=e1){ tempArr[k++] = array[s1++]; } while(s2<=e2){
tempArr[k++] = array[s2++]; } for (int i = 0; i < tempArr.length; i++) {
array[i+left] = tempArr[i]; } } public static void mergerSortInternall(int[]
array,int left,int right){ if(left>=right)return; int mid =
left+((right-left)>>>1); mergerSortInternall(array,left,mid);
mergerSortInternall(array,mid+1,right); merger(array,left,mid,right); } public
static void mergerSort(int[] array){
mergerSortInternall(array,0,array.length-1); } } public class MergerSort {
public static void main(String[] args) { Soultion soultion = new Soultion();
int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); soultion.mergerSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }
 

非递归实现归并排序 

 思路见下图

class Soultion{ public static void mergerSortInternall2(int[] array,int
left,int right){ int gap = 1; while(gap<array.length){ for (int i = 0; i <
array.length; i+=2*gap) { left = i; int mid = left+gap-1; if(mid>=
array.length){ mid = array.length-1; } right = mid+gap; if(right>=
array.length){ right = array.length-1; } merger(array,left,mid,right); }
gap*=2; } } public static void mergerSort(int[] array){
mergerSortInternall2(array,0,array.length-1); } } public class MergerSort {
public static void main(String[] args) { Soultion soultion = new Soultion();
int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); soultion.mergerSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }

非基于比较的排序

1.计数排序 

计数排序:统计相同元素出现的次数,根据统计结果将序列回收到原来的序列中

class Soultion{ public static void countSort(int[] array){ int maxValue =
array[0]; int minValue = array[0]; for (int i = 1; i < array.length; i++) {
if(array[i]>maxValue){ maxValue = array[i]; } if(array[i]<minValue){ minValue =
array[i]; } } int reage = maxValue-minValue+1; int[] count = new int[reage];
for (int i = 0; i < array.length; i++) { count[array[i]-minValue]++; } int k =
0; for (int i = 0; i < count.length; i++) { while(count[i]>0){ array[k++] =
i+minValue; count[i]--; } } } } public class CountSort { public static void
main(String[] args) { Soultion soultion = new Soultion(); int[] array = new
int[]{2,5,1,3,11,0,4,-1,-5,7}; System.out.println("排序前"+
Arrays.toString(array)); soultion.countSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }
 

 计数排序特点总结:

1.计数排序在数据范围集中时,效率很高,但是适用范围及场景有限

2.时间复杂度:O(MAX(N,范围))

3.空间复杂度:O(范围)

4.是一种稳定的排序

2.基数排序

基数排序是依次根据个位数、十位数、百位数......的大小来排序 ,最终的结果就是排好序的序列

思路:

1.根据所给序列,找到序列中数据的最大值,并求该值的位数。

2.创建十个队列,这里可以将队列形象为桶。根据数据每一位的值放在相应桶中

3.再将桶里面的数据依次取出来
class Soultion_{ public static int countlen(int data){ return
(data+"").length(); } public static int index(int num,int r){ int ret = 0; for
(int i = 1; i <=r ; i++) { ret = num%10; num/=10; } return ret; } public static
void sort(int[] array){ int max = array[0]; for (int i = 1; i < array.length ;
i++) { if(array[i]>max)max = array[i]; } int len = countlen(max);
LinkedList<Integer>[] list = new LinkedList[10]; for (int i = 0; i <
list.length; i++) { list[i] = new LinkedList<>(); } for (int i = 1; i <=len ;
i++) { for (int j = 0; j < array.length; j++) {
list[index(array[j],i)].offer(array[j]); } int k = 0; for (int j = 0; j <
list.length; j++) { while(!list[j].isEmpty()){ array[k++] = list[j].poll(); } }
} } } public class RadixSort { public static void main(String[] args) {
Soultion_ soultion = new Soultion_(); int[] arr = { 23, 1, 4, 9, 98, 132, 42 };
soultion.sort(arr); System.out.println(Arrays.toString(arr)); } }

基数排序特点总结:

1.时间复杂度O(n)

2.当元素取值范围较大,但元素个数较少时可以利用基数排序 

 

3.桶排序 

桶排序是根据所给序列中数据来划分区间,一个区间就是一个桶,将元素之间差值不大的放进一个桶中。然后对桶内数据进行排序,最后将排好序的桶内数据倒出给原来的数组。

思路见下图:

 
class Sort{ public static void bucketSort(int [] array){ int max =
Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i <
array.length; i++) { max = Math.max(max,array[i]); min =
Math.min(min,array[i]); } int reage = (max-min)/ array.length+1;
PriorityQueue<Integer>[] queue = new PriorityQueue[reage]; for (int i = 0; i <
reage; i++) { queue[i] = new PriorityQueue<>(); } for (int i = 0; i <
array.length; i++) { int num = (array[i]-min)/array.length;
queue[num].offer(array[i]); } int k = 0; for (int i = 0; i < queue.length; i++)
{ while(!queue[i].isEmpty()){ array[k++] = queue[i].poll(); } } } } public
class BucketSort { public static void main(String[] args) { Sort sort = new
Sort(); int[] array = new int[]{3,0,19,15,24,30}; System.out.println("排序前"+
Arrays.toString(array)); sort.bucketSort(array); System.out.println("排序后"+
Arrays.toString(array)); } }
 

桶排序特点总结:

1.时间复杂度O(N)

2.空间复杂度O(N+M)

3.不稳定 

技术
©2019-2020 Toolsou All rights reserved,
TypeScript:函数类型接口8道大厂指针笔试题让你秒杀指针!!!MySQL 日期时间加减mysql 查询条件之外的数据_mysql 查询符合条件的数据查linux的操作系统版本,如何查看Linux操作系统版本?将String类型转换成Map数据类型使用uuid做MySQL主键,被老板,爆怼一顿C语言中的字符串函数和字符函数linux服务器中毒排查--基础篇C# ASCII码字符转换