《数算》常见排序算法

1.冒泡排序

通过从头到尾比较前一位与后一位值arr[j]>arr[j+1]),交换数据(值),把最大的往后放。这样确保最后一个就是最大的,循环就可以减少1次。

因为前面确保了后面的数是放好的,那么后面的循环就可以不用比较了,arr.length-n-1(-1是因为前一位与后一位的比较,到倒数第2个的时候(j),它已经和最后一个比较了(j+1),如果再继续最后一个的话,比较n+1,那么就会越界,-1)

实现

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int arr[]){
for (int i = 0; i < arr.length; i++) {//一次内循环排好一个元素
for (int j = 0; j < arr.length-i-1; j++) {//每次比较的次数:第1次比较n-0-1次,第二次n-1-1,第三次n-2-1
if (arr[j]>arr[j+1]){//前一个和后一个的比较
//数据交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

测试

1
2
3
4
5
public static void main(String[] args) {
int arr[] = {1,2,8,6,7,64,16};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}

[1, 2, 6, 7, 8, 16, 64]

2.选择排序

和冒泡不同,选择排序先排最小的,从小到逐渐排序。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectSort(int arr[]){
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];//记录最小的值
int point = i;//记录最小的值的下标
for (int j = i+1; j < arr.length; j++) {
if (temp>arr[j]){
temp = arr[j];
point = j;
}

}
if (point==i) continue;//说明没有比当前小的
//交换数据,只需要交换一次
arr[point] = arr[i];
arr[i] = temp;

}

测试

1
2
3
4
5
public static void main(String[] args) {
int arr[] = {1,2,8,6,7,64,16};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}

[1, 2, 7, 6, 8, 16, 64]

3.插入排序

对于未排序的数据序列,在已排序序列中从后向前扫描,找到相应的位置并插入,类似打扑克牌时的码牌。插入排序有一种优化的算法,可以进行拆半插入。

​ 交换法

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort(int[]arr){
for (int i = 1; i < arr.length; i++) {
for (int j = i-1; j >=0; j--) {
if (arr[j]>arr[j+1]){
int temp =arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;

}
}
}
}

移动法

1
2
3
4
5
6
7
8
9
10
11
12
13
public static long insertSort2(int[]arr){
long start = System.currentTimeMillis();
for (int i = 1; i < arr.length; i++) {
int j = i;
int temp = arr[j];//当前的值
for ( ;j-1>=0&&temp<arr[j-1]; j--) {//如果当前小于要插入的值,就后移,直到j到了合适的位置
arr[j] =arr[j-1];//后移
}
arr[j] =temp;//交换
}
long end = System.currentTimeMillis();
return end-start;
}

移动法相比于交换法,只需要交换一次数据,所以效率较高

4.希尔排序

当插入排序对于大量无序(顺序较乱)的值排序时,效率较低。为了改进这一问题,希尔排序由此诞生。

希尔排序是根据递减增量(折半插入)来排序,效率高,但不稳定。

它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时

根据动态图可以看出来,每次增量都是拆半,第一次是中间,第二次是中间的一半….

假如定义一个长度为10数组int arr[]={12,94,3,45,16,32,19,15,18,14}; 那么它第一次进行插入排序的是从10/2=5开始 第三次是5/2=2开始,第三次是2/2=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void shellSort1(int[]arr){
//第一遍
int n = arr.length;
int h = n/2;//增量
for (int i =h; i <n ; i++) {
if (arr[i-h]>arr[i])
swap(arr,i, i-h);
}
//第二遍
h= h/2;
for (int i = h; i < n; i++) {
for (int j = i-h; j >=0; j-=2) {
if (arr[j]>arr[j+h])
swap(arr,j, j+2);
}
}
//第三遍
h = h/2;
for (int i = 0; i < arr.length; i++) {
for (int j = i-h; j >=0; j--) {
if (arr[j]>arr[j+h])
swap(arr,j, j+h);

}
}
}

测试

[3, 12, 18, 14, 15, 19, 16, 45, 32, 94]

简化后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort2(int[]arr){//10ms
int n = arr.length;
for (int grap = n/2; grap >0 ; grap/=2) {
for (int i = grap; i < arr.length; i++) {
for (int j = i-grap; j >=0; j-=grap) {
if (arr[j]>arr[j+grap]){
int temp =arr[j+grap];
arr[j+grap] = arr[j];
arr[j] = temp;

}
}
}
}
}

测试

[3, 12, 18, 14, 15, 19, 16, 45, 32, 94]

但是发现对数量大的值排序的时候,还不如冒泡排序,80000个数据希尔排序时间:9871ms,80000个数据,冒泡排序使用了9856 ms。这是因为,现在的希尔排序时间复杂度是 O(n log n),所以交换数据次数比冒泡还要多。

优化

使用移动法进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void shellSort2(int[]arr){//10ms
int n = arr.length;
for (int grap = n/2; grap >0; grap/=2) {
for (int i = grap; i < n; i++) {
//当前要插入的值和下标
int j = i;
int temp = arr[j];
for (;j-grap>=0&&arr[j]<arr[j-grap]; j-=grap) {//j-grap>=0说明前面还有元素,当前的<前一个 就让前一个往后移;直到移动到相应的位置。
arr[j] = arr[j-grap];
}
arr[j] = temp;

}
}
}

测试

80000个数据排序时间:17ms

另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void shellSort(int[] data) {
int h = 1;
while (h <= arrayLength / 3) {//
h = h * 3 + 1;//4
}
while (h > 0) {
System.out.println("===h的值:" + h + "===");
for (int i = h; i < arrayLength; i++) {
int temp = data[i];
if (data[i] - data[i - h] < 0) {
int j = i - h;
for (; j >= 0 && data[j] - temp > 0; j -= h) {
data[j + h] = data[j];
}
data[j + h] = temp;
}
// System.out.println(java.util.Arrays.toString(data));
}
h = (h - 1) / 3;
}
}

测试

80000个数据排序时间:20ms 和上一种差不多,可能会慢一点点

5.快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
找一个基数,以它为例,左边都是比基数小的,右边的都是比基数大的。
*/
public class QuickSort {

public static void main(String[] args) {
int arr[]=new int[80000];
for (int i = 0; i < arr.length; i++) {
arr[i] =(int) (Math.random()*8000000);
}
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length-1);
long end = System.currentTimeMillis();
System.out.println(end-start);
}

public static void quickSort(int []arr,int low,int high){//80000个数据30ms左右
if (low>=high)
return;
int p,i,j,temp;
p = arr[low];//基数
i = low;//从最左边开始的指针
j = high;//从最右边开始的指针
while (i<j){//如果左右两个指针相等,说明已经找完了
//右边的先走,这样让比基数大的全部全部都替换掉,只剩下比基数小的
while (arr[j]>=p&&i<j)//如果右指针的数比基数大就继续循环,直到找到比基数小的才停止循环
j--;
while (arr[i]<=p&&i<j)//如果右指针的数比基数小就继续循环,直到找到比基数大的才停止循环
i++;
temp = arr[i];
arr[i]= arr[j];
arr[j] = temp;
}
arr[low] = arr[i];
arr[i] = p;
quickSort(arr, low, j-1);//左边
quickSort(arr, j+1, high);//右边

}

}
6.归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class MergerSort {
public static void main(String[] args) {
int arr[]=new int[80000];

for (int i = 0; i < arr.length; i++) {
arr[i] =(int) (Math.random()*8000000);
}
System.out.printf("使用了:%dms\n",mergerSort(arr));
}
public static long mergerSort(int arr[]){//80000数据 20ms以下
int temp[] = new int [arr.length];//赋值到额外开辟的空间
long start = System.currentTimeMillis();
mergerSort(arr, 0, arr.length-1,temp);
long end = System.currentTimeMillis();
return end-start;
}

public static void mergerSort(int arr[],int left,int right,int temp[]){//80000数据 20ms以下
if (left==right) return; //变成只有一个的时候就开始回溯合并
int mid = (left+right)/2;
mergerSort(arr, left, mid, temp);//左边
mergerSort(arr, mid + 1, right, temp);//右边
merger(arr, left, mid, right, temp);//合并
}
public static void merger(int arr[],int left,int mid,int right,int temp[]){
int i,j,t;
i = left;//左边开始的指针
j=mid+1;//右边开始的指针
t=0;//辅助数组的索引位置

while (i<=mid&&j<right){
//那个小就把哪个先放进去
if (arr[i]<arr[j]) temp[t++]=arr[i++];
else temp[t++] = arr[j++];
}
while (i<=mid) temp[t++]=arr[i++];//复制左边剩余的
while (j<=right) temp[t++]=arr[j++];//复制右边剩余的

//复制
t=0;
i = left;
while (i<right) arr[i++] = temp[t++];
}
}

测试

输出

使用了:16ms

7.基数排序

数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用

基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

基数排序是对传统桶排序的扩展,速度很快。基数排序时稳定的。

注意:基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序时,容易造成 OutOfMemoryError 。有负数的数组,我们不用基数排序来进行排序, 如果要支持负数,取绝对值

基本思想:

1)将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class BaseSort {
public static void main(String[] args) {
int arr[]=new int[80000];
for (int i = 0; i < arr.length; i++) {
arr[i] =(int) (Math.random()*800000);
}
// int arr[]={12,94,3,45,16,32,19,15,18,14};
long start = System.currentTimeMillis();
baseSort(arr);
long end = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
System.out.println(arr[i]);
}
System.out.printf("使用了%d ms\n",end-start);

}


/**
* 根据数组每个元素的 每位数的基数来排序
* 然后再放入数组里
* @param arr
*/
public static void baseSort(int arr[]){//80000:30ms左右
int bucketCount = 10;//桶的数量
int bucket[][] =new int [bucketCount][arr.length];//桶
int max = arr[0];//最大值
for (int i = 1; i < arr.length; i++){
if (max<arr[i]) max =arr[i];
}
/*支持负数
int max = Math.abs(arr[0]);//最大值
for (int i = 1; i < arr.length; i++){
if (Math.abs(max)<Math.abs(arr[i])) max =Math.abs(arr[i]);
}
*/
int maxLength = (max+"").length();//取最大值的位数。
for (int i = 0; i <maxLength ; i++) {//按照位数来决定要放取多少次
int bucketInCount[] = new int[bucketCount];//记录每个桶的放了多少个
//放桶里
for (int j = 0; j < arr.length; j++) {
int base = arr[j]/(int) Math.pow(10, i)%10;
bucket[base][bucketInCount[base]++]=arr[j];
}
//放回数组
int index =0;//放入数组的下标
for (int j = 0; j < bucketCount; j++) {
if (bucketInCount[j]==0) continue;//没有就往下一个桶找
for (int k = 0; k < bucketInCount[j]; k++) {
arr[index++] = bucket[j][k];//放回数组
}
}
}
}
}
常用排序算法对比

根据需要来选择合适的算法进行排序

相关术语解释:

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

内排序**:所有排序操作都在内存中完成;**

外排序**:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;**

时间复杂度:一个算法执行所耗费的时间。

空间复杂度:运行完一个程序所需内存的大小。**

n:数据规模

k:“桶”的个数

In-place**:** 不占用额外内存

Out-place:占用额外内存

参考文章

动态图片来源:尚硅谷资源