常见排序算法（Java代码实现）

前言

学习算法和数据结构必备算法逻辑动态演示网站，收藏到就是赚到，链接: 数据结构动态演示网站
下面的代码单独理解会比较抽象，建议结合动态演示学习，更加直观

常见排序算法（时间复杂度）

O(n^2)：冒泡排序、插入排序、选择排序
O(nlogn)：归并排序、快速排序

1、冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足则让它两个交换

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

2、插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。

public static void insertSort(int[] numbers){
	 int length = numbers.length;
	 for (int i = 1; i < length; i++) {
	     int j = i-1;
	     int value = numbers[i];
	     for (; j>=0; j--){
	        if (numbers[j] > value){
	            numbers[j+1] = numbers[j];
	        }
	        else{
	            break;
	        }
	    }
	    numbers[j+1] = value;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、选择排序

选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。

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

4、归并排序

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

public static void mergeSort(int[] numbers,int left,int right){
    if (left>=right){
        return;
    }
    int middle = (left+right)/2;
    mergeSort(numbers,left,middle);
    mergeSort(numbers,middle+1,right);

    mergeSortTemp(numbers,left,middle,right);
}
//归并排序工具类
private static void mergeSortTemp(int[] numbers, int left, int middle, int right) {
    int[] temps = new int[right-left+1];
    int tempsSize=0;
    int left0 = left;
    int left1 = middle+1;
    while (left0<=middle && left1<=right){
        if (numbers[left0]<=numbers[left1]){
            temps[tempsSize++] = numbers[left0++];
        }else{
            temps[tempsSize++] = numbers[left1++];
        }
    }
    while (left0 <= middle){
        temps[tempsSize++] = numbers[left0++];
    }
    while(left1 <= right){
        temps[tempsSize++] = numbers[left1++];
    }
    for (int i = 0; i <= right - left; i++) {
        numbers[left+i] = temps[i];
    }
}
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

5、快速排序

如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

public static void quickSort(int[] numbers,int left,int right){
     if (left > right){
         return;
     }
     int i = left;
     int j = right;
     int base = numbers[left];
     while(i != j){
         while(numbers[j]>=base && i<j){
             j--;
         }
         while(numbers[i]<=base && i<j){
             i++;
         }
         int temp;
         temp = numbers[i];
         numbers[i] = numbers[j];
         numbers[j] = temp;
     }
     numbers[left] = numbers[i];
     numbers[i] = base;
     quickSort(numbers,left,i-1);
     quickSort(numbers,i+1,right);
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24