- 排序算法
- 1、冒泡排序
- 2、选择排序
- 3、插入排序
- 4、希尔排序
- 5、归并排序
原理：每一次比较，都将大的数往后排；每一轮比较，都能筛选出本轮的最大数排到数组的末尾。
稳定性：稳定
复杂度：冒泡排序是稳定的，由于该排序算法的每一轮都要遍历一遍所有的元素，轮转的次数和元素数量相当，所以时间复杂度为O(N^2)。因为不占用额外的存储空间，所以空间复杂度为O(1)。
算法描述：
假设有无序随机数组：[5,4,2,6,7,8,1,3,9]
第一轮比较：
第一轮第一次：5和4比较，5>4，进行位置交换。此时数组：[4,5,2,6,7,8,1,3,9]
第一轮第二次：5和2比较，5>2，进行位置交换。此时数组：[4,2,5,6,7,8,1,3,9]
第一轮第三次：5和6比较，5<6，不进行位置交换。此时数组：[4,2,5,6,7,8,1,3,9]
第一轮第四次：6和7比较，6<7，不进行位置交换。此时数组：[4,2,5,6,7,8,1,3,9]
第一轮第五次：7和8比较，7<8，不进行位置交换。此时数组：[4,2,5,6,7,8,1,3,9]
第一轮第六次：8和1比较，8>1，进行位置交换。此时数组：[4,2,5,6,7,1,8,3,9]
第一轮第七次：8和3比较，8>3，进行位置交换。此时数组：[4,2,5,6,7,1,3,8,9]
第一轮第八次：8和9比较，8<9，不进行位置交换。此时数组：[4,2,5,6,7,1,3,8,9]
第一轮结束，排序后筛选出了第一轮的最大值9，放到了数组的末尾。
第二轮比较：
第二轮第一次：4和2比较，4>2，进行位置交换。此时数组：[2,4,5,6,7,1,3,8,9]
第二轮第二次：4和5比较，4<5，不进行位置交换。此时数组：[2,4,5,6,7,1,3,8,9]
第二轮第三次：5和6比较，5<6，不进行位置交换。此时数组：[2,4,5,6,7,1,3,8,9]
第二轮第四次：6和7比较，6<7，不进行位置交换。此时数组：[2,4,5,6,7,1,3,8,9]
第二轮第五次：7和1比较，7>1，进行位置交换。此时数组：[2,4,5,6,1,7,3,8,9]
第二轮第六次：7和3比较，7>3，进行位置交换。此时数组：[2,4,5,6,1,3,7,8,9]
第二轮第七次：7和8比较，7<8，不进行位置交换。此时数组：[2,4,5,6,1,3,7,8,9]
第二轮结束，排序后筛选出了第二轮的最大值8，放到了数组的次末尾，本次排序的末尾。
…
总共需要进行n轮比较，假设当前比较的轮次为i，则当前轮次进行比较的次数为n-i-1，
计算时间复杂度
t
=
n
∗
(
n
−
i
−
1
)
=
n
2
−
i
n
−
n
=
n
2
t=n*(n-i-1)=n^2-in-n=n^2
t=n∗(n−i−1)=n2−in−n=n2,即
t
=
O
(
n
2
)
t=O(n^2)
t=O(n2)
代码实现：（注：算法千千万，这里只是其中一种）
private static void bubbleSort(int[] arr){
long ctmie=System.currentTimeMillis();
if(arr==null||arr.length<2){
return;
}
for(int i=0;iarr[k+1]){
arr[k]=arr[k]^arr[k+1];
arr[k+1]=arr[k]^arr[k+1];
arr[k]=arr[k]^arr[k+1];
}
}
}
System.out.println("耗时="+(System.currentTimeMillis()-ctmie)+"ms");
}
2、选择排序
原理：首先在未排序数组中找到最小（大）元素，存放到排序数组的起始位置。接下来每一次循环都从未排序的那一部分数组中选择出最大或者最小值放到已排序的那一部分数组。
稳定性：不稳定
复杂度：无论什么数据进去都是 O(n^2) 的时间复杂度。但是不占用额外的内存空间，所以空间复杂度是O(1)
算法描述：
假设有无序随机数组：arr[3,2,8,7,2,9,5]
第一轮排序，假设最小值为数组的第一个值3，下标为0；
第一次比较，3>2，最小值替换为2，下标为1；
第二次比较，2<8,不变；
第三次比较，2<7，不变；
第四次比较，2=2，不小于2，最小值替换为2，下标为4；
第五次比较，2<9，不变；
第六次比较，2<5，不变；
最后进行值交换，将数组的第一个值和当前记录的最小值进行交换，即arr[0]=arr[4]=2，arr[4]=arr[0]=3。此时数组为arr[2,2,8,7,3,9,5]
第二轮排序，最小值为arr[1]=2，下标为1；
第一次比较，2<8，不变；
第二次比较，2<7，不变；
第三次比较，2<3,不变；
第四次比较，2<9,不变；
第五次比较，2<5，不变；
此时数组为arr[2,2,8,7,3,9,5]
第三轮排序，最小值为arr[2]=8,下标为2；
第一次比较，8>7,最小值替换为7，下标为3；
第二次比较，7>3,最小值替换为3，下标为4；
第三次比较，3<9,不变；
第四次比较，3<5，不变；
最后进行值交换，将数组第三个值即下标为2的值和当前记录的最小值进行交换，即arr[2]=arr[4]=3,arr[4]=arr[2]=8。此时数组为arr[2,2,3,7,8,9,5]
…
总共需要进行n-1轮比较，假设当前比较轮次为i，则本轮比较的次数为n-i-1,计算时间复杂度为
t
=
(
n
−
1
)
∗
(
n
−
i
−
1
)
=
n
2
−
i
n
−
2
n
+
i
+
1
=
n
2
t=(n-1)*(n-i-1)=n^2-in-2n+i+1=n^2
t=(n−1)∗(n−i−1)=n2−in−2n+i+1=n2,即
t
=
O
(
n
2
)
t=O(n^2)
t=O(n2)
算法实现：（算法千千万，这里只是其中一种）
private static void selectedSort(int[] arr){
long ctmie=System.currentTimeMillis();
if(arr==null||arr.length<2){
return;
}
for(int i=0;iarr[j]){
minIdx=j;
}
}
if(minIdx==i){
continue;
}
arr[i]=arr[i]^arr[minIdx];
arr[minIdx]=arr[i]^arr[minIdx];
arr[i]=arr[i]^arr[minIdx];
}
System.out.println("耗时="+(System.currentTimeMillis()-ctmie)+"ms");
}
3、插入排序
原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
稳定性：稳定
复杂度：时间复杂度O(n^2)，空间复杂度：O(1)
算法描述：
假设有无序随机数组：arr[3,5,8,1,7,9,4]
第一轮排序，将arr[0]作为有序数组，剩余的作为无序数组，取下标为1的值5存临时值并对有序数组从右往左进行循环比较，当前有序数组就一个元素，即arr[0]=3,此时5>3,不需要移动元素，只需要把5追加到有序数组尾部即可，即arr[1]=arr[1]=5，此时有序数组为[3,5],无序数组为[8,1,7,9,4]。整体数组为[3,5,8,1,7,9,4]
第二轮排序，取下标为2的值存临时值8并对有序数组从右往左进行循环比较，此时8>5，不需要移动元素，只需要把8追加到有序数组尾部即可，即arr[2]=arr[2]=8，此时有序数组为[3,5,8],无序数组为[1,7,9,4]。整体数组为[3,5,8,1,7,9,4]
第三轮排序，取下标为3的值存临时值1并对有序数组从右往左进行循环比较，此时1<8,需要将8后移一位为1腾出位置，即arr[3]=arr[2]=8,然后接着比较，此时,1<5,需要将5后移一位为1腾出位置，即arr[2]=arr[1]=5,然后接着比较，此时1<3,需要将3后移一位为1腾出位置，即arr[1]=arr[0]=3,这时候已经循环到有序数组的头部，所以将1赋值给arr[0],即arr[0]=1，此时有序数组为[1,3,5,8]，无序数组为[7,9,4]。整体数组为[1,3,5,8,7,9,4]
第四轮排序，取下标为[4]的值7存临时值并对有序数组从右往左进行循环比较，此时7<8,需要将8后移一位为7腾出位置，即arr[4]=arr[3]=8,然后接着比较，此时7>5,不需要接着往后比较，直接将7赋值给arr[3],然后结束本轮循环。此时有序数组为[1,3,5,7,8]，无序数组为[9,4],整体数组为[1,3,5,7,8,9,4]
…
总共需要n-1轮比较，假设当前轮次为i，则本轮比较的次数平均为i，计算时间复杂度
t
=
(
n
−
1
)
∗
i
t=(n-1)*i
t=(n−1)∗i，当i趋近于n时，
t
=
(
n
−
1
)
∗
n
=
n
2
−
n
=
n
2
t=(n-1)*n=n^2-n=n^2
t=(n−1)∗n=n2−n=n2,即
t
=
O
(
n
2
)
t=O(n^2)
t=O(n2)
算法实现：（算法千千万，这里只是其中一种）
private static void insertSort(int[] arr){
long ctmie=System.currentTimeMillis();
if(arr==null||arr.length<2){
return ;
}
for(int i=1;i0&&val
4、希尔排序
原理：优化后的插入排序，将整个序列分成若干个小序列，然后采用增量递减法，对每个小序列都进行插入排序，当增量为1的时候，小序列即为整个序列，在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >…> d[t] = 1 (t趟排序)，这里注意，分开的每个小序列不是紧挨着的，而是按照增量组合的，具体看算法描述。可以理解为先局部排序后整体排序。
稳定性：不稳定
复杂度：时间复杂度和增量的选择有关，有研究出的时间复杂度范围为O(n^(1.3~2))，空间复杂度O(1)
算法描述：
假设有无序数组：[7,6,2,8,1,9,3,54,8,10,32,18],初始选择的分段增量为arr.length/2，即12/2=6.
第一轮排序：将整个序列分为6个小序列，即[7,3],[6,54],[2,8],[8,10],[1,32],[9,18],对这些小序列进行排序，排序后的结果为:[3,7],[6,54],[2,8],[8,10],[1,32],[9,18],整个数组序列为[3,6,2,8,1,9,7,54,8,10,32,18]。
然后再对增量除以2，即6/2=3.
第二轮排序：将整个序列分为3个小序列，即[3,8,7,10],[6,1,54,32],[2,9,8,18],对这些小序列进行排序，排序后的结果为：[3,7,8,10],[1,6,32,54],[2,8,9,18],此时整个数组序列为[3,1,2,7,6,8,8,32,9,10,54,18]。
然后再对增量除以2，即3/2=1.
第三轮排序，因为增量为1，此时小序列就是整个序列，对该数组序列进行插入排序，排序后的结果为：[1,2,3,6,7,8,8,9,10,18,32,54]。
假设分段的系数为k，数组长度为n，则每轮小序列个数为
m
=
n
/
k
或
者
n
/
(
k
2
)
或
者
n
/
(
k
i
)
m=n/k或者n/(k^2)或者n/(k^i)
m=n/k或者n/(k2)或者n/(ki)，即
m
=
n
/
(
k
i
)
m=n/(k^i)
m=n/(ki),每轮需要进行n-m次比较，所以时间复杂度为
t
=
(
n
−
m
)
∗
(
n
/
k
i
)
t=(n-m)*(n/k^i)
t=(n−m)∗(n/ki),因为k不定但是一个常数，且
1
<
=
k
i
<
n
1<=k^i
算法实现：（算法千千万，这里只是其中一种）
private static void shellSort(int[] arr){
if(arr==null||arr.length<2){
return;
}
int length = arr.length;
int val,j;
long ctime=System.currentTimeMillis();
for(int gap=length/2;gap>0;gap/=2){
for(int i=gap;i=0&&val
5、归并排序
原理：该算法是分治法思想的一个典型应用，将整个数组序列分成若干个小的序列，然后自底向上对序列进行排序归并，最终归并成为一个排好序的序列。
稳定性：稳定
复杂度：时间复杂度O(n log n)，空间复杂度：O(n)，因为需要构建一个与原数组空间一样大的空数组存放排序后的数组
算法描述：
假设有无序数组：[2,5,8,3,6,9,23,7,2,6,4],
该算法需要构造两个函数，一个数分函数，一个是合函数。
分函数：（一直分，直到子数组只有一个元素为止）
第一轮，因为数组长度为11,11/2=5，所以中位数为5，将整个数组分成两部分，即[2,5,8,3,6,9]和[23,7,2,6,4]。
第二轮，左边数组长度为6,6/2=3，左边中位数为3，将左边数组分成两部分，即[2,5,8]和[3,6,9]；右边数组长度为5,5/2=2,右边中位数为2，将右边数组分成两部分，即[23,7]和[2,6,4]
第三轮，同样的规律，可分为数组: [[2,5],[8]],[[3,6],[9]],[[23,7],[2]],[[6],[4]]
第四轮，同样的规律，可分为数组: [[[2],[5]],[8]],[[[3],[6]],[9]],[[[23],[7]],[2]],[[6],[4]]
注意这里的中括号，这里的每一个中括号都代表一层，到时候合并数组是要从内往外合并的。
最后可以看出，最内层被分成了一个个数组长度为1的小数组,即
[[[2],[5]],[8]],[[[3],[6]],[9]],[[[23],[7]],[2]],[[6],[4]]
但是自底向上合并时是有规律的。
合函数：（一直合，一边合一边排序，知道合成一个完整的数组）
第一轮，根据上边分函数的结果进行合并排序，[2][5]合并成[2,5]，然后[2,5]和[8]合并成[2,5,8]，然后是[3][6]合并成[3,6],[3,6]和[9]合并成[3,6,9]，[2,5,8]和[3,6,9]合并成[2,3,5,6,8,9]，此时左边已经合并完成，[23][7]合并成[7,23]，[7,23][2]合并成[2,7,23]，[6][4]合并成[4,6],[2,7,23][4,6]合并成[2,4,6,7,23]此时右边合并完成，最后合并[2,3,5,6,8,9]和[2,4,6,7,23]，最终结果为[2,2,3,4,5,6,6,7,8,9,23]
数组长度为n，一次拆分合并的耗时为
t
(
n
)
=
2
∗
t
(
n
/
2
)
+
n
t(n)=2*t(n/2)+n
t(n)=2∗t(n/2)+n，其中t(n)表示对n个数进行归并排序，替换公式可得，
t
(
n
)
=
2
∗
(
2
∗
t
(
n
/
4
)
+
n
/
2
)
+
n
=
2
2
∗
t
(
n
/
4
)
+
2
n
=
.
.
.
.
=
2
k
∗
t
(
n
/
2
k
)
+
k
n
t(n)=2*(2*t(n/4)+n/2)+n=2^2*t(n/4)+2n=....=2^k*t(n/2^k)+kn
t(n)=2∗(2∗t(n/4)+n/2)+n=22∗t(n/4)+2n=....=2k∗t(n/2k)+kn,当
2
k
2^k
2k趋近于n时，即
n
/
2
k
=
1
n/2^k=1
n/2k=1,可得
k
=
l
o
g
2
n
k=log_2n
k=log2n代入上式,
t
(
n
)
=
2
l
o
g
2
n
∗
t
(
1
)
+
n
l
o
g
2
n
t(n)=2^{log_2n}*t(1)+nlog_2n
t(n)=2log2n∗t(1)+nlog2n,因为
t
(
1
)
=
0
t(1)=0
t(1)=0,所以
t
(
n
)
=
n
l
o
g
2
n
t(n)=nlog_2n
t(n)=nlog2n,即时间复杂度为
t
=
O
(
n
l
o
g
2
n
)
t=O(nlog_2n)
t=O(nlog2n)
算法实现：（算法千千万，这里只是其中一种）
private static int[] mergeSort(int[] arr){
if(arr==null||arr.length<2){
return arr;
}
long ctime=System.currentTimeMillis();
int mid=(arr.length-1)/2;
int[] a= splitSubSort(0,mid,arr.length-1,arr);
System.out.println("耗时="+(System.currentTimeMillis()-ctime)+"ms");
return a;
}
private static int[] splitSubSort(int start,int mid,int end,int[] arr){
//System.err.println(start+"=="+mid+"=="+end);
if(start==mid&&end==mid){
return new int[]{arr[mid]};
}
int lMid=(mid+start)/2;
int rMid=(end+mid+1)/2;
return mergeSubSort(splitSubSort(start,lMid,mid,arr),splitSubSort(mid+1,rMid,end,arr));
}
private static int[] mergeSubSort(int[] arrLeft,int[] arrRight){
int[] arr=new int[arrLeft.length+arrRight.length];
int count=0,l=0,r=0;
while(l
