THIS IS B3c0me

记录生活中的点点滴滴

0%

排序算法

发表于 更新于 分类于

1.排序的分类

  • 内部排序：
    • 需要将处理的所有数据都加载到内部存储器中进行排序
  • 外部排序：
    • 数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

常见的排序算法分类：

  • 内部排序
    • 插入排序
      • 直接插入排序
      • 希尔排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 归并排序
    • 技术排序
  • 外部排序

2.算法的时间复杂度

  • 事后统计法

    • 需要实际运行改程序
    • 所得时间的统计量依赖于计算机的硬件、软件等环境因素

  • 事前估算法

    • 通过分析某个算法的时间复杂度来判断哪个算法更优
2.1 时间频度

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n).

2.2 时间复杂度

常见的时间复杂度：

  • 常数阶O(1)
    • 没有循环等复杂结构，这个代码的时间复杂度就是常数阶
  • 对数阶
  • 线性阶
  • 线性对数阶
    • 将时间复杂度为指数阶的代码执行N次
  • 立方阶
    • 嵌套三层相同次数的循环
  • k次方阶
  • 指数阶
2.3 平均时间复杂度

是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间

2.4 最坏时间复杂度

所有案例均按最大时间复杂度计算

3.算法的空间复杂度

  • 一个算法的空间复杂度定义为该算法所小号的存储空间，她也是问题规模n的函数
  • 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
  • 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重程序的执行速度。一些缓存产品和算法本质就是空间换时间。

4.冒泡排序

4.1 基本思想：

通过对待排序序列从前向后，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后

排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此在排序过程中设置一个标志判断元素是否进行过交换

4.2 代码实现

80000个数据排序耗时10s

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 com.datastructure.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

public class BubbleSort {
    public static void main(String[] args) {
        //创建80000个数据的数组
        int [] arr1 = new int[80000];
        Random random = new Random();
        for(int i = 0; i < 80000; i ++){
            arr1[i] = random.nextInt(8000000)+1;//生成(0,8000000的数）
        }

        //记录排序前的时间
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = simpleDateFormat.format(date);
        System.out.println("排序前的时间："+ dateStr);
        //测试冒泡程序
        int[] ints = bubbleSort(arr1);
        System.out.println(Arrays.toString(ints));//输出执行结果
        //执行完后的时间
        Date date1 = new Date();
        String dateStr1 = simpleDateFormat.format(date1);
        System.out.println("排序后的时间："+ dateStr1);
    }
    //将冒泡排序算法封装成一个方法
    public static int[] bubbleSort(int[] arr1) {
        int temp = 0;
        int [] arr = arr1;
        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]) {
                    flag = true;//如果进来过则说明进行了排序
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (flag == false) {
                //说明在一趟排序中一次交换都没有发生
                break;
            } else {
                flag = false;//重置flag,进行下一趟排序
            }
        }
        return arr;
    }
}

5.选择排序

属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

5.1 基本思想
  • 第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换
  • 第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换
  • 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换
  • 总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
5.2 代码实现

80000个数据排序耗时2s

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

import java.util.Arrays;

public class SelectSorting {

    public static void main(String[] args) {
        int[] arr = {11,22,65,1,2,64,72,3,5,16,43,21,52};
        selectSort(arr);
    }

    public static int[] selectSort(int[] arr){
        int[] arr1 = arr;
        for(int i = 0; i < arr1.length -1 ; i++){
            int minIndex = i;
            int min = arr1[i];
            for(int j = i + 1; j < arr1.length; j++){
                if(min > arr1[j]){
                    min = arr1[j];
                    minIndex = j;
                }
            }
            if(minIndex != i){
                arr1[minIndex] = arr1[i];
                arr1[i] = min;
            }
            System.out.println("第"+(i+1)+"轮之后的结果是：");
            System.out.println(Arrays.toString(arr1));
        }
        return arr1;
    }
}

6.插入排序

6.1 基本思想

​ 把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码一次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

6.2 代码实现

80000个整数排序耗时4s

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

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int [] arr1 = {5,6,4,1,2,3,5,4,12,65,2,31};
        insertSort(arr1);
    }

    public static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            //定义待插入的数
            int insertVal = arr[i];
            //定义待插入的位置
            int insertIndex = i - 1;
            //退出while循环时，找到待插入的位置
            while (insertIndex >=0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;
            System.out.println("第"+i+"轮插入：");
            System.out.println(Arrays.toString(arr));
        }
    }
}

7.希尔排序

简单插入排序存在的问题：

当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。

7.1 介绍

希尔排序也是一种插入排序，是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

7.2 基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序：

随着增量主键减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

7.3 代码实现

  • 交换式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public static void shellSort1(int[] arr){
           int temp = 0;
           int count = 0;
           for(int gap = arr.length / 2; gap > 0; gap /= 2){
               for(int i = gap; i < arr.length; i++){
                   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("第"+(++count)+ "轮排序的结果为：" + Arrays.toString(arr));
           }
       }

  • 移位式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public static void shellSort2(int[] arr){
            int temp = 0;
            int count = 0;
            for(int gap = arr.length / 2; gap > 0; gap /= 2){
                for(int i = gap; i < arr.length; i++){
                    int j = i;
                    temp = arr[j];
                    if(arr[j] < arr[j - gap]) {
                        //while循环找到待插入的位置
                        while(j - gap >= 0 && temp < arr[j - gap]){
                            arr[j] = arr[j - gap];
                            j -= gap;
                        }
                        arr[j] = temp;
                    }
                }
                System.out.println("第"+(++count)+ "轮排序的结果为：" + Arrays.toString(arr));
            }
        }

8.快速排序

8.1 算法介绍

快速排序是对冒泡排序的一种改进。

8.2 算法思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，一次达到整个数据变成有序序列。

8.3 代码实现
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
public static void quikSort(int[] arr,int left,int right){
        //中轴值
        int l = left;
        int r = right;
        int pivot = arr[ (l + r) / 2];
        //让比pivot小的值放到左边
        //比pivot大的 值放到右边
        int temp = 0;
        while( l < r){

            while(arr[l] < pivot){
                //在pivot的左边找到一个大于等于pivot的值
                l += 1;
            }
            while(arr[r] > pivot){
                //在pivot的右边找到一个小于等于pivot的值
                r -= 1;
            }
            if(l >= r){
                //说明pivot的左右两边的值，已将按照左边全都是小于pivot的值，右边全都是大于pivot的值
                break;
            }
            //交换两边的值
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
            //如果交换完后发现arr[l]==pivot,r--
            if(arr[l] == pivot){
                r -= 1;
            }
            if(arr[r] == pivot){
                l += 1;
            }
        }
        //如果 l == r;必须l++,r--;否则会出现栈溢出
        if(l == r){
            l +=1;
            r-=1;
        }
        //向左递归
        if(left < r){
            quikSort(arr,left,r);
        }
        //向右递归
        if(right > l){
            quikSort(arr,l,right);
        }
    }

9.归并排序

9.1 基本介绍

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

9.2 基本思想

分而治之

9.3 代码实现
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
package com.datastructure.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);
           //向右递归进行分解
           mergeSort(arr,mid+1,right,temp);
           //到合并
           merge(arr,left,mid,right,temp);
       }
    }

    //合并的方法
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int l = left;//初始化i，表示左边有序序列的初始索引
        int r = mid + 1;//表示右边有序序列的初始索引
        int t = 0;//依次指向temp的索引

        //先把左右两边的数据（有序）按规则拷贝到temp，直到左右两边的有序序列有一边处理完毕为止
        while(l <= mid && r<= right){
            if(arr[l] <= arr[r]){
                temp[t] = arr[l];
                t+=1;
                l+=1;
            } else {
                temp[t] = arr[r];
                t+=1;
                r+=1;
            }
        }
        //如果另一边有剩余，就把剩余的所有元素拷贝到temp后面
        while( l <= mid){
            temp[t] = arr[l];
            t+=1;
            l+=1;
        }
        while( r <= right){
            temp[t] = arr[r];
            t+=1;
            r+=1;
        }
        //将temp重新拷贝到arr
        t = 0;
        int tempLeft = left;
        while(tempLeft <= right){
            arr[tempLeft] = temp[t];
            t +=1;
            tempLeft +=1;
        }
    }

}

欢迎关注我的其它发布渠道