基础排序算法介绍

基础排序算法介绍

知识点:

  • 排序算法稳定性的定义：简单的介绍就是排序前相等的数据先后顺序在排序后的先后顺序位置相同

  • 基本交换算法

    1
    2
    3
    4
    5
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

  • 时间复杂度：执行算法所需要的计算工作量 $ O(1) $ 意味没有循环即只执行单条语句 $ O(n) $ 执行没有嵌套的循环 $ O(n^2) $ 双重嵌套循环

  • 空间复杂度：算法在运行工程中临时占用存储空间的量度
算法 平均时间 最好 最差 空间复杂度 稳定性
冒泡排序 $ O(n^2) $ $ O(n) $ $ O(n^2) $ $ O(1) $ 稳定
直接插入排序 $ O(n^2) $ $ O(n) $ $ O(n^2) $ $ O(1) $ 稳定
折半插入排序 $ O(nlogn) $ $ O(nlogn) $ $ O(n^2) $ $ O(1) $ 稳定
希尔排序 $ O(nlogn) $ - $ O(n^2) $ $ O(n^1.3) $ $ O(n^2) $ $ O(1) $ 不稳定
选择排序 $ O(n^2) $ $ O(n^2) $ $ O(n^2) $ $ O(1) $ 不稳定
快速排序 $ O(nlogn) $ $ O(nlogn) $ $ O(n^2) $ $ O(nlogn) $ - $ O(n^2) $ 不稳定
归并排序 $ O(nlogn) $ $ O(nlogn) $ $ O(nlogn) $ $ O(n) $ 稳定
堆排序 $ O(nlogn) $ $ O(nlogn) $ $ O(nlogn) $ $ O(1) $ 不稳定

排序算法

冒泡排序

在要排序的一组数中，对当前范围内还未排列好的数据由上而下进行比较，即每当相邻的数与要求的排序方式相反时将数据进行互换
改进版的写法就是利用标记法减少循环次数

基本写法

1
2
3
4
5
6
7
8
9
10
private static void bubbleSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 1; j < size - i; j++) {
                if (array[j - 1] > array[j]) {
                    swap(array, j, j - 1);
                }
            }
        }
    }

改进写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void advancedBubbleSort(int[] array) {
        int size = array.length;
        int flag = 0;//设置标记位
        for (int i = 0; i < size - 1; i++) {
            flag = 0;
            for (int j = 1; j < size - i; j++) {
                if (array[j - 1] > array[j]) {
                    flag = 1;
                    swap(array, j, j - 1);
                }
            }
            if (flag == 0)//没有发生数据交换则意味着排序已经结束
                break;
        }
    }

选择排序

再一次遍历过程中找到最小值放在排序数据中的首位，每次寻找剩余中最小的直到结束为止。

1
2
3
4
5
6
7
8
9
10
11
12
private static void selectSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size; i++) {
            int minIndex = i;
            for (int j = i + 1; j < size; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

直接插入排序

按照顺序选定元素从后往前找，插入一个顺序数列中即可

1
2
3
4
5
6
7
8
9
10
private static void InsertSort(int[] array) {
       int size = array.length;
       for (int i = 0; i < size; i++) {
           int temp = array[i];
           for (int j = i; j > 0 && array[j - 1] > array[j]; j--) {//从该元素所在位置 向前移动 直到该元素位于 递增顺序
               array[j] = array[j - 1];
               array[j - 1] = temp;
           }
       }
   }

折半插入排序

再往前寻找位置的过程中利用二分法寻找位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void insertBinarySort(int[] array) {
        int size = array.length;
        for (int i = 1; i < size; i++) {
            if (array[i] < array[i - 1]) {//前比后大
                int temp = array[i];
                int low = 0, high = i - 1, mid;
                while (low <= high) {//直到相交或者相反
                    mid = (low + high) / 2;//折中取点
                    if (temp < array[mid]) {//小于中点则位于中点左侧
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                for (int j = i; j > low; j--) {
                    array[j] = array[j - 1];
                }
                array[low] = temp;//低点使用temp
            }
        }
    }

希尔排序

先取d为间隔，将原始数组分为d个序列，将间隔的数组放在一个子序列利用插入排序法进行排序 然后缩小间隔d 重复上述操作，知道d为1时，则排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
private static void shellSort(int[] array) {
        int size = array.length;
        for (int d = size / 2; d > 0; d /= 2) {//设置步长
            for (int i = 0; i < size; i += d) {
                int temp = array[i];
                int j = i;
                for (; j >= d && temp < array[j - d]; j -= d) {
                    array[j] = array[j - d];
                }
                array[j] = temp;
            }
        }
    }

基数排序

讲一组元素进行桶分配，按照每位数的大小进行排序

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
private static void radixSort(int[] array) {
    int size = array.length;
    int max = array[0];//数组中的最大数
    for (int i = 0; i < size; i++) {
        if (array[i] > max)
            max = array[i];
    }

    int time = 0;//最大位数
    while (max > 0) {
        max /= 10;
        time++;
    }

    int k = 0;//索引
    int m = 1;//位值
    int n = 1;//第几位

    int[][] temp = new int[10][size];
    int[] order = new int[10];

    while (m <= time) {
        for (int arr : array) {
            int lsd = (arr / n) % 10;
            temp[lsd][order[lsd]] = arr;
            order[lsd]++;
        }

        for (int i = 0; i < 10; i++) {
            if (order[i] != 0) {
                for (int j = 0; j < order[i]; j++) {
                    array[k] = temp[i][j];
                    k++;
                }
            }
            order[i] = 0;
        }

        n *= 10;
        k = 0;
        m++;
    }
}

快速排序

通过排序将待排序记录分成两部分，其中一部分记录的关键字均比另一部分小，然后分别对这两部分进行排序，直到整个序列有序。快速排序在元素很少时，效率很低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void quickSort(int[] arr,int l,int r){
    if(l>=r)
        return;
    int p=getMiddle(arr,l,r);//取出中点
    quickSort(arr,l,p-1);//对左侧进行排序
    quickSort(arr,p+1,r);//对右侧进行排序
}

    private static int getMiddle(int[] arr, int l, int r) {
        int temp = arr[l];//定义左侧为基点
        int middle = l;
        for (int i = middle + 1; i <= r; i++) {
            if (arr[i] < temp) {
                swap(arr, middle + 1, i);
                middle++;
            }
        }
        swap(arr, l, middle);
        return middle;
    }

归并排序

把待排序序列分成若干个有序子序列，然后再把子序列合并成一个有序序列。

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
private static void mergeSort(int[] arr, int l, int r) {
    int mid = (l + r) / 2;
    if (l < r) {
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    //左指针
    int i = low;
    //右指针
    int j = mid + 1;
    int index = 0;
    //把较小的数 移动到新数组中
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[index++] = arr[i++];
        } else {
            temp[index++] = arr[j++];
        }
    }
    //把左边剩余的数移到新数组中
    while (i <= mid) {
        temp[index++] = arr[i++];
    }
    //把右边剩余的数移到新数组中
    while (j <= high) {
        temp[index++] = arr[j++];
    }
    //得到新的数据 覆盖原有部分
    System.arraycopy(temp, 0, arr, low, temp.length);
}

堆排序

将数组构成大堆二叉树，即父节点比子节点大的二叉树，然后每次将根节点放在最后一位，循环遍历

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
/**
 * 堆排序
 * @param arr
 */
private static void heapSort(int[] arr) {
    //预先构建一次大堆二叉树
    buildMaxHeap(arr);
    int length = arr.length;
    for (int i = length - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeap(arr, i, 0);
    }
}
/**
 * 
 */
private static void buildMaxHeap(int[] arr) {
    int length = arr.length;
    for (int i = length / 2 - 1; i >= 0; i--) {
        maxHeap(arr, length, i);
    }
}

/**
 * 构建大堆二叉树节点
 */
private static void maxHeap(int[] arr, int length, int node) {
    int left = 2 * node + 1;
    int right = 2 * node + 2;

    int maxIndex = node;
    if (left < length && arr[left] > arr[maxIndex]) {
        maxIndex = left;
    }
    if (right < length && arr[right] > arr[maxIndex]) {
        maxIndex = right;
    }
    //如果不是父节点最大，则找到最大的子节点进行调换
    if (maxIndex != node) {
        swap(arr, node, maxIndex);
        maxHeap(arr, length, maxIndex);
    }

}
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！