Java常见排序算法

发表于 本文字数： 12k 阅读时长 ≈ 11 分钟

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
		int[] a = {6,9,7,3,1};
		for (int i = 0; i < a.length-1; i++) {
			for (int j = 0; j < a.length-i-1; j++) {
				if(a[j]>a[j+1]) {
					int temp =a[j];
					a[j] = a[j+1];
					a[j+1] =temp;
				}
			}
		}
		System.out.println(Arrays.toString(a));
}

选择排序

  1. 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数与第一个元素交换
  2. 第二次遍历n-2个数，找到最小的数值与第二个元素交换
  3. 重复以上步骤
  4. 第n-1词遍历，找到最小的数值与第n-1的元素交换，排序完成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
		int[] a = {8,2,3,17,23,85,1,9};
		for (int i = 0; i < a.length; i++) {
            //定义此轮循环最小数放置的位置
            int minIndex = i;
            //从第2个数依次和后面的数进行对比
			for (int j = i+1; j < a.length; j++) {
                //如果minIndex的数比j大则记录j
				if(a[minIndex]>a[j]) {
					minIndex=j;
				}
			}
            if(minIndex!=i){
                int temp = a[minIndex];
                a[minIndex] = a[i];
                a[i] = temp;
                System.out.println("每次结果>>>"+Arrays.toString(a));
            }
			System.out.println("每轮结果==="+Arrays.toString(a));
		}
	}

插入排序

  1. 在要排序的无序数组中，假定n-1个数已经排好序，现在将第n个数插入到前面的有序数列中，使得这个n个数也是拍好序的，反复循环，直到全部排好顺序。插入排序也可以理解为从第二个数开始，前面的相邻的数依次两两对比，如果后面的数比前面的数小，则交换位置。（如果实在理解不了，可以类比冒泡排序，把插入排序理解为一种特殊的冒泡排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
		int[] a = {87,86,82,10,30};
		for (int i = 0; i < a.length-1; i++) {
			for (int j = i+1; j >0; j--) {
				if(a[j]<a[j-1]) {
					int temp = a[j];
					a[j] = a[j-1];
					a[j-1] = temp;
				}else{
                	break;   
                }
				System.out.println("每次结果==="+Arrays.toString(a));
			}
			System.out.println("第"+(i+1)+"轮结果>>>"+Arrays.toString(a));
		}
	}

快速排序

快速排序有两种实现方式：双边循环法和挖坑法，思路如下：
快速排序

  1. 定义左右指针，并选取一个数作为基准（通常选择数组第一个）
  2. 移动右指针，如果右指针的数小于基准数，则停止移动，反之则继续移动
  3. 移动左指针，如果左指针的数大于基准数，则停止移动，反之则继续移动
  4. 当左右指针都停止移动时交换左右指针处的数
  5. 当左右两个指针停在相同位置时，交换指针处的数和基准数的位置
  6. 将数组以左右指针位置处一分为二重复上述步骤。
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
	/**
	 * 双边循环
	 * @return
	 */
	public static int pivotIndex(int[]ary,int startIndex,int endIndex) {
		//保存左右两个指针，从第一个元素和最后一个元素开始
		int left = startIndex;
		int right = endIndex;
		//获取基准，一般选择数组第一个数
		int pivot = ary[startIndex];
		//大循环，当左右两个指针不相等时，左指针右移，右指针左移
		while (left!=right) {
			//右边指针向左移动，当对应元素大于基准数时继续移动，小于基准数时停止移动
			while(right>left&&ary[right]>=pivot) {
				right--;
			}
			//左边指针向右移动，当小于基准数时继续移动，大于基准数时停止移动
			while (right>left&&ary[left]<=pivot) {
				left++;
			}
			//此时如果左边指针小于右边指针时；左右指针交换元素
			if(left<right) {
				int temp = ary[right];
				ary[right] = ary[left];
				ary[left] = temp;
			}
		}
		int index = left;
		//如果两个指针相等时,交换基准元素和当前位置的数
		ary[startIndex] = ary[index];
		ary[index] = pivot;
		return index;
	}
	public static void qucikSort(int[] ary,int startIndex,int endIndex) {
		if(startIndex>endIndex) {
			return;
		}
		int index = pivotIndex(ary,startIndex,endIndex);
		qucikSort(ary, startIndex, index-1);
		qucikSort(ary, index+1, endIndex);
	}
	public static void main(String[] args) {
		int[] a= {5,6,1,2,4,9,3};
		qucikSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
	}
}

挖坑法

  1. 选取起始位置作为标记位（也就是坑），选取一个数作为基准，通常是数组第一个
  2. 从数组第二数开始依次和基准数对比，如果比基准数小，则扩大小于基准数的区间，也就是mark++，并将该数与标mark处的数交换
  3. 循环结束后，将mark处的数和基准数进行交换
  4. 以mark为界，将数组一分为二重复上述步骤

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
/**
 * 单边循环
 * @author MR.W
 */
public class QucikSort2 {
	public static int pivotIndex(int[] ary,int startIndex,int endIndex) {
		int mark = startIndex;
		int pivot = ary[startIndex];
		for (int i = startIndex+1; i <= endIndex; i++) {
			//如果指针指向的元素小于基准元素，干两件事情
			//1.mark+1,扩大小于基准数的区间
			//2.将指针所指向的数和mark位置处的数进行交换
			if(ary[i]<pivot) {
				mark++;
				int temp = ary[i];
				ary[i] = ary[mark];
				ary[mark] = temp;
			}
		}
		//当循环结束时将mark位置的数和基准数进行交换
		ary[startIndex]= ary[mark]; 
		ary[mark] = pivot;
		return mark;
	}
	public static void quickSort(int[] ary,int startIndex,int endIndex) {
		if(startIndex>endIndex) {
			return;
		}
		int index = pivotIndex(ary, startIndex, endIndex);
		quickSort(ary, startIndex, index-1);
		quickSort(ary, index+1, endIndex);
	}
	public static void main(String[] args) {
		int [] a = {7,9,1,4,8};
		quickSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void main(String[] args) {
		
		int [] a = {5,1,6,2,3};
		
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length-1; j++) {
				int temp;
				if(a[i]<a[j]) {
					temp = a[j];
					a[j] = a[i];
					a[i] = temp;
				}
				System.out.println("每次"+Arrays.toString(a));
			}
			System.out.println("每轮"+Arrays.toString(a));
		}
		System.out.println("最后"+Arrays.toString(a));
	}

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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
public class ShellSort {    
    public static int[] shellSort(int ary[],int length){
        int temp = 0;
        int gap = length;
        while(true){
            gap = gap/2;
            //根据增量将数组分为若干子序列
            //K表示第几个子序列
            for(int k = 0;k<gap;k++){
                //对子序列插入排序
                for(int i = k+gap;i<length;i+=gap){
                    //因为是相隔gap的元素插入排序，所以j-=jap
                    for(int j=i;j>k;j-=gap){
                        if(ary[j]<ary[j-gap]){
                             temp = ary[j-gap];
                             ary[j-gap] = ary[j];
                             ary[j] = temp;
                        }else{
                            break;
                        }
                        System.out.println("每次结果：>>>"+Arrays.toString(ary)); 
                    }
                System.out.println("每轮结果：---"+Arrays.toString(ary));
                }
            }
            if(gap==1){
                break;
            }
        }
        return ary;
    }

    public static void main(String[] args) {
        int[] ary = {3,8,9,1,2,5,7,6};
        System.out.println(Arrays.toString(shellSort(ary, ary.length)));
    }

}

基数排序

基数排序的思路非常简单，首先创建数组，然后将每个数放到相应的位置（例如6放在下标为6的数组位置）；最后遍历数组，即为排序后的结果。

  1. 基数排序先排好个位，然后排好在排好个位的基础上排十位，以此类推，直到遍历最高位次，排序结束。

  2. 基数排序不是比较排序，而是通过分配和收集的过程来实现排序。

  3. 初始化10个桶，桶下标为0-9

  4. 通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中

  5. 基数排序有两种排序方式：LSD和MSD，最小位有限（从右边开始）和最大位优先（从左边开始）。

    ​

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
public class RadixSort {
private static void radixSort(int[] array,int d)
{
    int n=1;//代表位数对应的数：1,10,100...
    int k=0;//保存每一位排序后的结果用于下一位的排序输入
    int length=array.length;
    int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
    int[] order=new int[length];//用于保存每个桶里有多少个数字
    while(n<d)
    {
        for(int num:array) //将数组array里的每个数字放在相应的桶里
        {
            int digit=(num/n)%10;
            bucket[digit][order[digit]]=num;
            order[digit]++;
        }
        for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
        {
            if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
            {
                for(int j=0;j<order[i];j++)
                {
                    array[k]=bucket[i][j];
                    k++;
                }
            }
            order[i]=0;//将桶里计数器置0，用于下一次位排序
        }
        n*=10;
        k=0;//将k置0，用于下一轮保存位排序结果
    }
}

归并排序

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

  1. 把长度为n的数组分成两个长度为n/2的子序列
  2. 对这两个子数组分别采用归并排序
  3. 将两个排序号的子数组合并成一个最终的排序数组

首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁。

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
import java.util.Arrays;

public class MergeSort {
    public static void sort(int ary[]){
        int[] temp = new int[ary.length];
        sort(ary,0,ary.length-1,temp);
    }

    public static void sort(int[] ary,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2;
            //左侧子数组归并排序
            sort(ary,left,mid,temp);
            //右侧子数组归并排序
            sort(ary,mid+1,right,temp);
            //合并子数组
            merge(ary, left, mid, right, temp);
        }
    }

    private static void merge(int[] ary,int left,int mid,int right,int[]temp){
        //左指针序列
        int i = left;
        //右指针序列
        int j = mid+1;
        //临时指针
        int t = 0;
        while(i <= mid && j <= right){
            if(ary[i]<=ary[j]){
                temp[t++]=ary[i++];
            }else{
                temp[t++]=ary[j++];
            }
        }
        //将左边剩余的元素填充进temp中
        while(i<=mid){
            temp[t++]=ary[i++];
        }
        //将右边剩余元素填充进temp中
        while(j<=right){
            temp[t++] = ary[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组
        while(left<=right){
            ary[left++] = temp[t++];
        }
    }
    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
**大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] **
**小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] **
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

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
public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

  1. 计数排序的特征
    当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
    由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
    通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 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
public class CountingSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

}

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
元素分配在桶中：

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
56
57
58
59
60
61
62
63
64
public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

常见排序的复杂度