排序：排序就是对某项数据按照特定的要求，比如大小或字符长短等按照升序或降序排序。
排序过程中设计稳定性，稳定性指的是若有两个相同的数字，比如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.不稳定
转载：https://blog.csdn.net/yahid/article/details/125413176