Fork me on GitHub

算法--排序

字数统计: 4k字   |   阅读时长≈ 17分

排序

  1. 直接插入排序：选取无序区的一个元素找到在有序区的插入位置，插入有序区（排扑克牌的过程）

  • 平均时间复杂度：O(n^2)

  • 空间复杂度：O(1)

  • 稳定性：稳定

    avatar

    avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 插入排序
  * @param arr
  */
public void insertSort(int[] arr) {
  //初始第一个元素为有序区，第二个数开始作为无序区，逐渐缩小无序区，扩大有序区
    for (int i = 1; i < arr.length; i++) {
        int val = arr[i];//每轮取无序区第一个数作为待插入元素
        int j=i-1;//有序区最后
        //寻找插入位置索引，在有序区最后从后往前检索
        while (j>=0&&val<arr[j]){
            arr[j+1]=arr[j];
            j--;
        }
        //找到插入位置
        if (j != i - 1) {
            arr[j + 1] = val;
        }
    }
}


2. 希尔排序（缩小增量法）：（直接插入排序优化）先选定一个整数gap（步长），把待排序序列中所有元素（n个）分成gap个组，所有距离为gap的元素分在同一组内，并对每一组内的元素进行直接插入排序。然后将gap逐渐减小，重复上述分组和排序的工作，当到达gap=1时，排序前的数据已将近正序，所有元素在统一组内排好序，gap=0时结束。（效率高于直接插入排序，但不稳定）

  • 平均时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

取gap=n/2为例：

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void shellSort(int[] arr) {
    for (int gap = arr.length >> 1; gap > 0; gap = gap >> 1) {//缩小步长
        //直接插入排序（原直接插入排序相当于步长为1的情况，所以对原插入排序有1的地方改为gap即可）
        for (int i = gap; i < arr.length; i++) {
            int val = arr[i];
            int j=i-gap;
            while (j>=0&&val<arr[j]){
                arr[j+gap]=arr[j];
                j-=gap;
            }
            if (j != i - gap) {
                arr[j + gap] = val;
            }
        }
    }
}


3. 冒泡排序：每一轮从头开始，从前往后两两元素进行比较，前一个比后一个大就交换，直到将最大的元素交换到末尾位置，每轮减少一个元素

  • 平均时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定

avatar

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
  /**
   * 冒泡排序
   * @param arr
   */
public void bubbleSort(int[] arr){
    boolean isSwap=false;//看一轮中是否交换过元素，如果没交换过，则说明序列有序，不用进行后面的轮
    for (int i = 0; i < arr.length-1; i++) {//最后一轮只剩一个元素，不用进行
        for (int j = 0; j < arr.length - i-1; j++) {//每轮最后一个元素不用往后比较
            if (arr[j]>arr[j+1]){
                swap(arr,j,j+1);
                isSwap=true;
            }
        }
        if (!isSwap){
            break;
        }
        isSwap=false;
    }
}

/**
 * 交换
 * @param arr
 * @param i
 * @param j
 */
private void swap(int[] arr, int i, int j) {
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}


4. 快速排序：基于分治思想排序，将某元素作为基准值，把比基准值小的调整到基准值左边，递归切分基准值左右两部分，按同样规则进行调整

  • 平均时间复杂度:O(nlogn)
  • 空间复杂度:O(logn)
  • 稳定性:不稳定

调整具体思路是：

  • 选定一个基准值（为了方便选区间最左边那个）
  • 确定两个指针 l 和 r，分别从区间两边向中间走,r指针找比基准值小的，l指针找比基准值大的，指针移动时，让r指针先走
  • 两指针停下后交换对应位置的值
  • 继续向下走，重复以上步骤，直到两指针重合时，最后将基准值与重合位置值进行交换。

为什么要让r指针先走？

最后是要把相遇位置处的数和基准位置处的数进行交换，要保证交换到基准值位置的数比基准值小，如果让l指针（找大的）先走，l指针先停下，两指针相遇时会找到一个比基准值大的数和基准值交换，所以得让r指针（找小的）先走

[6,1,2,7,9,3,4,5,10,8]调整过程：

avatar

完整快速排序过程：

avatar

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
/**
 * 快速排序
* @param arr
*/
public void quickSort(int[] arr){
    split(arr,0,arr.length-1);
}

/**
 * 切分
* @param arr
* @param left
* @param right
*/
private void split(int[] arr,int left,int right){
    if (left>=right){
        return;
    }
    int p=partition(arr,left,right);
    split(arr,left,p-1);//切分基准值左半部分
    split(arr,p+1,right);//切分基准值右半部分
}

/**
 * 小于基准值的调整到基准值左边
* @param arr
* 区间
* @param left
* @param right
* @return 交换后的基准值索引
*/
private int partition(int[] arr, int left, int right) {
    int i=left;
    int j=right;
    int pv=arr[left];//每次为区间最左边的那个
    while (i<j){
        while (i<j&&arr[j]>pv){//找比基准值小的
            j--;
        }
        while (i<j&&arr[i]<=pv){//找比基准值大的
            i++;
        }
        swap(arr,i,j);
    }
    swap(arr,left,i);
    return i;
}

/**
 * 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}


5. 选择排序：每轮在区间中选择一个最小的排在该轮区间最前面

  • 平均时间复杂度：O(n^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

avatar

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
/**
 * 选择排序
* @param arr
*/
public void selectSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        int min = findMin(arr, i);
        swap(arr,i,min);
    }
}

/**
 * @param arr
* @param left
* @return 数组区间从[left~最后一个元素]最小值索引
*/
private int findMin(int[] arr,int left){
    int minVal=arr[left];
    int minIndex=left;
    for (int i = left+1; i <arr.length; i++) {
        if (minVal>arr[i]){
            minVal=arr[i];
            minIndex=i;
        }
    }
    return minIndex;
}

/**
 * 交换
* @param arr
* @param i
* @param min
*/
private void swap(int[] arr, int i, int min) {
    int temp=arr[i];
    arr[i]=arr[min];
    arr[min]=temp;
}


6. 堆排序：每轮将待排的无序序列调整成堆结构，将堆顶最值交换到最后，每轮减少一个元素

  • 基本思路：
  • 升序采用大顶堆（由于大根堆每轮最大的会被交换到最后，形成升序序列），降序采用小顶堆
  • 首先将待排序的数组调整成一个堆（大根堆/小根堆），此时，整个数组的最大（小）值就是堆顶
  • 将堆顶元素与末尾的元素交换，此时，末尾的元素为最大（小）值，剩余待排序序列个数为n-1个
  • 将剩余的n-1个数再调整成堆（大根堆/小根堆），由于交换后只有堆顶元素不符合堆结构，所以对堆顶元素执行下潜即可，再将堆顶元素与n-1位置的元素交换，如此反复执行，便能得到有序序列
  • 平均时间复杂度：O(nlogn)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

堆：一种完全二叉树

  • 大顶堆：每个父结点的值都大于其左右孩子的值
  • 小顶堆：每个父结点的值都小于其左右孩子的值

avatar

数组表示：

avatar

数组中某个元素的父结点及其左右孩子索引:

  • 父节点索引为i
  • 左孩子索引：2*i+1
  • 右孩子索引：2*i+2（左孩子索引+1）
  • 孩子索引为j
  • 父节点索引：(j-1)/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
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
/**
 * 堆排序
* @param arr
*/
public void heapSort(int[] arr){
    heapify(arr);//建堆
    int size=arr.length;
    while (size>1){//交换堆顶元素和末尾元素
        swap(arr,0,size-1);
        size--;
        down(arr,0,size);//重新调整堆结构
    }
}

/**
 * 建堆
* @param arr
*/
private void heapify(int[] arr) {
    //从后往前第一个非叶子结点开始下潜（弗洛伊德建堆O(logn)）（另一种威廉姆斯建堆，边添加结点边调整堆结构O(nlogn)）
    for (int i = arr.length / 2 - 1; i >=0 ; i--) {
        down(arr,i,arr.length);
    }
}

/**
 * 下潜
* @param arr
* @param i 开始结点索引
* @param n 结束索引
*/
private void down(int[] arr, int i,int n) {
    int max=i;
    int left=i*2+1;//左孩子索引
    int right=left+1;//右孩子索引
    //父节点和左右孩子中选一个最大的（大顶堆）（若选最小的为小顶堆）
    if (left<n&&arr[max]<arr[left]){
        max=left;
    }
    if (right<n&&arr[max]<arr[right]){
        max=right;
    }
    if (max!=i){
        swap(arr,i,max);
        down(arr,max,n);//继续下潜
    }
}

/**
 * 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}


7. 归并排序：基于分治思想的排序算法

  • 思想
  • 分：切分原始数组（向下）
  • 治：两子序列合并成有序序列
  • 合：有序序列继续和其他序列合并（向上）
  • 平均时间复杂度：O(nlogn)
  • 空间复杂度：O(n)
  • 稳定性：稳定

avatar

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
/**
 * 归并排序
* @param arr
*/
public void mergeSort(int[] arr){
    if (arr.length==0){
        return;
    }
    int[] temp=new int[arr.length];
    split(arr,0,arr.length-1,temp);
}

/**
 * 切分
* @param arr
* @param left 左边界
* @param right 右边界
* @param temp 临时数组，合并时用
*/
private void split(int[] arr, int left, int right,int[] temp) {
    if (left==right){
        return;
    }
    int mid=left+right>>>1;
    split(arr,left,mid,temp);//左半部分切分
    split(arr,mid+1,right,temp);//右半部分切分
    merge(arr,left,mid,mid+1,right,temp);//合并成有序序列(结果在临时数组中)
    System.arraycopy(temp,left,arr,left,right-left+1);//合并结果存回原数组，继续合并
}

/**
 * 合并（数组两区间合并成有序序列存于临时数组中）
* @param arr
* @param left
* @param leftEnd
* @param right
* @param rightEnd
* @param temp
*/
private void merge(int[] arr, int left, int leftEnd, int right, int rightEnd,int[] temp) {
    int i=left;
    int j=right;
    int k=left;
    while (i<=leftEnd&&j<=rightEnd){
        if (arr[i]<arr[j]){
            temp[k]=arr[i];
            i++;
        }else {
            temp[k]=arr[j];
            j++;
        }
        k++;
    }
    if (j>rightEnd){
        System.arraycopy(arr,i,temp,k,leftEnd-i+1);
    }
    if (i>leftEnd){
        System.arraycopy(arr,j,temp,k,rightEnd-j+1);
    }
}


8. 计数排序：使用一个count[]数组来统计原数组每个元素出现的个数，count数组值作为元素个数值，索引作为元素值(索引和元素值之间的关系为相对值，不一定与元素值相等，建立一种映射关系)，再根据个数把对应元素写回原数组

  • 平均时间复杂度：O(n+k) （k为count[]大小，n元素个数）
  • 空间复杂度：O(k)
  • 稳定性：可稳定或不稳定

avatar

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
/**
 * 只针对元素大于0计数排序（可通过此理解和改写成通用版本）
* @param arr
*/
public void countSort(int[] arr){
    //求最大
    int max=arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (max<arr[i]){
            max=arr[i];
        }
    }
    //计数数组
    int[] count=new int[max+1];
    //统计元素个数
    for (int i : arr) {
        count[i]++;
    }
    //写回原数组
    int j=0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]>0){
            arr[j++]=i;
            count[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
/**
 * 计数排序
* @param arr
*/
public void countSort(int[] arr){
    //求最大最小值
    int max=arr[0];
    int min=arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (max<arr[i]){
            max=arr[i];
        }
        if (min>arr[i]){
            min=arr[i];
        }
    }
    //计数数组
    int[] count=new int[max-min+1];
    //统计元素个数
    for (int i : arr) {
        count[i-min]++;
    }
    //写回原数组
    int j=0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]>0){
            arr[j++]=i+min;
            count[i]--;
        }
    }
}


9. 桶排序：将数组元素分散到多个桶，保证索引小的桶装小的元素，索引大的桶装大的元素，然后进行桶内排序后，接着按顺序取桶，最后把桶内元素写回原数组

  • 平均时间复杂度：O(n+k) (k为桶个数，n为元素个数)
  • 空间复杂度：O(n+k)
  • 稳定性：稳定

avatar

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
/**
 * 桶排序（此版本结合计数排序方便理解和改进）
* @param arr
*/
public void bucketSort(int[] arr){
    //求最大值和最小值，max-min得数据范围
    int max=arr[0];
    int min=arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i]>max){
            max=arr[i];
        }
        if (arr[i]<min){
            min=arr[i];
        }
    }
    //初始化桶（max-min+1为数据范围内的每个数分配一个桶）
    ArrayList[] buckets=new ArrayList[max-min+1];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i]=new ArrayList();
    }
    //将数组元素分散到桶（元素值-min可以分配到对应桶且桶内元素只有一个，元素和桶具有映射关系
    // ->和计数排序类似，这样保证了小桶装小元素，大桶装大元素，因为只有一个元素，所以可以不用进行桶内排序
    // 所以按顺序取桶，写元素即可，但空间浪费大）
    for (int i : arr) {
        buckets[i-min].add(i);
    }

    int k=0;

    for (ArrayList bucket : buckets) {
        //桶内排序
        //bucket.sort(Comparator.comparingInt(o -> (Integer) o));

        //将桶内元素放回原数组
        for (Object o : bucket) {
            arr[k]= (int) o;
            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
/**
 * 桶排序（改进版）
* @param arr
* @param range 控制桶的数量和桶内元素个数
*/
public void bucketSort(int[] arr,int range){
    //求最大值和最小值，max-min得数据范围
    int max=arr[0];
    int min=arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i]>max){
            max=arr[i];
        }
        if (arr[i]<min){
            min=arr[i];
        }
    }
    //初始化桶（max-min+1为数据范围内的每个数分配一个桶） （除range减少桶数量）
    ArrayList[] buckets=new ArrayList[(max-min)/range+1];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i]=new ArrayList();
    }
    //将数组元素分散到桶（元素值-min可以分配到对应桶且桶内元素只有一个，元素和桶具有映射关系
    // ->和计数排序类似，这样保证了小桶装小元素，大桶装大元素，且只有一个元素
    // 所以这样按顺序取桶元素，可以不用进行桶内排序，但空间浪费大）
    for (int i : arr) {
        //（除range约束多个元素为一组，减少桶数量，桶内有多个元素了，所以得进行桶内排序）
        buckets[(i-min)/range].add(i); 
    }

    int k=0;

    for (ArrayList bucket : buckets) {
        //桶内排序
        bucket.sort(Comparator.comparingInt(o -> (Integer) o));

        //将桶内元素放回原数组
        for (Object o : bucket) {
            arr[k]= (int) o;
            k++;
        }
    }
}


10. 基数排序：以下采用LDS，即从个位开始，从右向左对每一位进行排序。初始化[0 ~ 9]个桶，刚开始按个位大小将每个元素分散到对应的桶（个位为0的装入0号桶，以此类推），个位分散完之后，再按桶顺序取出元素写回原数组，再进行下一轮百位的排序，以此类推。

  • 平均时间复杂度：O(k*n) (k位数，n元素个数)
  • 空间复杂度：O(m) (m桶个数)
  • 稳定性：稳定
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
/**
 * 基数排序（LDS 从右向左）
*
* @param arr
*/
public void radixSort(int[] arr) {
    if (arr.length == 0) {
        return;
    }
    //初始化[0~9]个桶
    ArrayList[] buckets = new ArrayList[10];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList();
    }

    //求最大值和最小值位数，位数大的为处理次数
    int max = arr[0];
    int min = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int maxBit = (max + "").length();
    int minBit = (min + "").length() - 1;
    int n = Integer.max(maxBit, minBit);

    //个位->百位->千位···的顺序进行
    int m = 1;
    for (int i = 0; i < n; i++) {
        //取数组元素分散到对应桶
        for (int ele : arr) {
            ele = ele - min;//负数也可以转换为>0的数，保证有桶可装
            int j = ele / m % 10;
            buckets[j].add(ele);
        }

        //按桶顺序将桶内元素取出放回原数组，进行下一轮分散到桶
        int k = 0;
        for (ArrayList bucket : buckets) {
            for (Object ele : bucket) {
                arr[k++] = (int) ele + min;//还原元素原始值
            }
            bucket.clear();//清空桶
        }

        m *= 10;
    }

java中Arrays.sort()根据数据量不同和特性采用不同排序算法。

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java开发

联系QQ:1445911979

如有错误，请帮忙指正，谢谢大家~~