排序算法

冒泡排序

冒泡排序其实就是通过遍历发现前后两个数的顺序不同而后交换实现如同冒泡一般的调序过程

要比较n(n-1)/2次——时间复杂度为O(n^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
55
package it01.sort;

public class maopao {
    public static void main(String[] args) {
        int[] arr = {1,3,5,4};
        bubbleSort(arr);
    }
    
	//1、两次for循环实现 注意加flag标志优化 无递归版本
    public static void bubbleSortWithDoubleFor(int[] arr){
        boolean flag = false;
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if (!flag){
                // 一次交换都没有发生 代表已经排好序了  不用再去进行n-1趟
                // eg：三次排完后已成有序则无需进行第四次判断
                break;
            }else {
                flag = false;// 如果进去了要进行flag重置，保证下一次排序正常判断
            }
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }

    //2、有递归版本 一层for 但是如果flag不符合要求则需要递归再进行一次for
    public static void bubbleSort(int[] arr){
        boolean flag = false;
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                flag = true;
            }
        }
        if(flag){
           bubbleSort(arr);
        }else {
            return;
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

选择排序

img

选择排序就是先定义最开始（第一个）的数为最小值，然后从后面的数选择比他小的数然后与他交换，然后逐层遍历下去。

交换移动次数少，但是还是要比较n(n-1)/2次 时间复杂度是交换和比较次数的总和为**O(n^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
package it01.sort;

public class selectsort {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 4};
        Selectsort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
    public static void Selectsort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minindex = i;
            int min = arr[i];
            for (int j = i+1; j < arr.length-1 ; j++) {
                if(min>arr[j]){
                    minindex = j;
                    min = arr[j];
                }
            }
            if(minindex!=i){
                int temp = arr[i];
                arr[i] = min;
                arr[minindex] = temp;
            }
        }
    }
}

插入排序

插入排序类似于你打扑克时整理牌时对牌的排序

时间复杂度为O(n^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
package it01.sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1,5,99,45648,456465,87461,15,0};
        //insertSort(arr);
        insertSortAll(arr);
    }

    public static void insertSortAll(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertIndex = i - 1; // 待插入数据的前一个位置 一开始默认第一个为有序数列
            int  insertValue = arr[i]; //把当前的数先存储起来备用
            //while循环意思是要找到要插入的位置
            //>=0是保证给待插入的数据找插入位置保证不越界
            // 同时要insertIndex后移
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                //把待插入数据的前一个数赋给下一个来供交换
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //退出while说明找到了要插入的位置
            // insertIndex要加一的原因就是你初始化insertIndex时就是待插入数据的前一个位置
            arr[insertIndex + 1] = insertValue;
        }
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组进行比较直接插入排序算法排序。其中增量序列的最后一个增量必须等于1。该排序是不稳定的，时间复杂度为O(n^3/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
package it01.sort;

import java.util.Arrays;

public class xier {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        YiWeiSort(arr);
    }

    //交换法希尔排序
    public static void xierSort(int[] arr) {
        //可以一轮轮进行推演运算 例如把gap=5代入
        // 首先要确立增量序列gap这里可以通过for循环不断除2得到 但他必须大于0
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            int temp = 0;//临时变量存储
            //gap一分为二 gap为后半部分同时i++  则前部分为i-gap
            for (int i = gap; i < arr.length; i++) {
                //二次循环结束条件为gap不断减少直至为0 同时j要大于0
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果不合顺序就交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    //移位法希尔排序
    public static void YiWeiSort(int[] arr) {
        //可以一轮轮进行推演运算 例如把gap=5代入
        // 首先要确立增量序列gap这里可以通过for循环不断除2得到 但他必须大于0
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                //二次循环结束条件为gap不断减少直至为0 同时j要大于0
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

快速排序

快排基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的，可以说是冒泡排序的升级版（本质上是交换排序类）（过程可递归进行）

时间复杂度O (nlogn) 但是空间复杂度较高——比较常用

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
package it01.sort;

import java.util.Arrays;

public class quickSort {
    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-567,70};

//        quickSort(arr, 0,arr.length-1 );
        System.out.println("arr: "+ Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right){
        int l = left;
        int r = right;
        int temp = 0; //临时变量
        // pivot 中轴
        int pivot = arr[(left + right) / 2];
        while (l<r){
            while (arr[l]<pivot){
                l++;
            }
            while (arr[r]>pivot){
                r--;
            }
            if(l>=r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            // 这里就是如果交换完后如果前面的值和中值相等 就不用和后面的值比较了避免死循环
            // 判断 如果交换完后发现arr[l] = pivot r向前移动 r--
            if(arr[l]==pivot){
                r--;
            }else if(arr[r]==pivot){
                //如果交换完后发现arr[r] = pivot l向后移动 l--
                l++;
            }
        }
        if(l==r){
            l++;
            r--;
        }
        // 向左递归---r指针会不断左走直到不小于left时递归退出
        if (left < r) {
            quickSort(arr,left,r);
        }
        // 向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

基数排序(桶排序)

基数排序就是把数组的每个数按照个位十位百位那些位数排序到对应的桶里，一层层进行升序排序的过程。是典型的空间换时间的排序算法。

时间复杂度O(nlogn) 如果有负数就不使用基数排序

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
package it01.sort;

import java.util.Arrays;

public class radixsort {
    public static void main(String[] args) {
        int [] arr = {1,8,1,864,13,135};
        radixSortAll(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void radixSortAll(int[] arr){
        int[][] bucket = new int[10][arr.length];
        int[] bucketElementCounts = new int[10];
        int index;
        // 需要获取最大的数便于遍历取余（最大限度）
        int max = arr[0];
        for (int i = 1; i < arr.length; i++){
            if (max < arr[i]){
                max = arr[i];
            }
        }
        int maxLength = (max+"").length();//数字加个空字符串就能利用字符串的长度方法找到最大数的位数
        for (int i = 0,n = 1; i < maxLength; i++,n*=10) {
            for (int j = 0; j < arr.length; j++) {
                //对应位数上的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶 对应位数上是二就放进2号桶
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                // 放进元素要++后移
                bucketElementCounts[digitOfElement]++;
            }
            // 将桶里的数据放入
            index = 0;
            // 遍历每一个桶 将桶里的数据放入 原来的数组中
            for (int k = 0;k < bucket.length; k++){
                if (bucketElementCounts[k] != 0){
                    for (int j = 0; j < bucketElementCounts[k]; j++){
                        arr[index++] = bucket[k][j];
                    }
                }
                bucketElementCounts[k]= 0;
            }
        }
        }
    }

归并排序

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
65
66
67
68
69
70
71
package it01.sort;

import java.util.Arrays;

public class mergesort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] temp = new int[arr.length]; // 归并排序需要额外的空间
        mergeSort(arr, 0, arr.length-1, temp);
        System.out.println(Arrays.toString(arr));

    }
    //最终分+合的归并方法 利用递归实现
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left < right) {
            //分解
            int mid = (left + right) / 2; // 中间的索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            // 向右递归进行分解 右边序列的第一个就是要mid+1
            mergeSort(arr, mid+1, right, temp);


            // 每次分解之后 合并一次！！！
            merge(arr, left, mid, right,temp);
        }
    }

    /**
     *  合并的方法
     * @param arr 原始的数组
     * @param left 左边有序序列的初始索引
     * @param mid  中间索引
     * @param right 右边索引
     * @param temp  中转数组
     */
    public static void merge(int[] arr,int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        //1、
        // 先把左右两边(有序)的数据 按照规则填充到temp
        // 直到左右两边的有序序列有一方处理完毕
        while (i <= mid && j <= right){
            // 如果左边的有序序列的当前元素 <= 右边有序序列的当前元素 将左边的当前元素放到temp的t的位置
            if (arr[i] <= arr[j]){
                temp[t++] = arr[i++];// 放入后移
            }else {
                temp[t++] = arr[j++];
            }
        }
        // 2、
        // 将有剩余的数组的数据一次加入temp中的尾部
        while (i <= mid){ //左边的有序序列还有剩余的数据 将剩余的有序数据 依次加入temp数组
            temp[t++] = arr[i++];
        }
        while (j <=right){ //右边的有序序列还有剩余的数据 将剩余的有序数据 依次加入temp数组
            temp[t++] = arr[j++];
        }
        //3、
        // 将temp数组重新放到arr
        // 注意 并不是每次拷贝所有
        t = 0;
        int tempLeft = left;
        // 第一次合并时 tempLeft=0 right=1 //  第二次合并 tempLeft=2 right=3 //  第三次合并tempLeft=0 right=3
        //  最后一次合并  tempLeft=0 right=7
        while (tempLeft <= right){
            arr[tempLeft++] = temp[t++];
        }
    }
}