浅谈排序算法(上)

计算机也许是快的,但它们不是无限快。储存器也许是廉价的,但不是免费的。
——strein《算法导论》
浅谈排序算法(上)

有一句话这么说:程序=数据结构+算法,可见算法在软件研发过程中的重要地位,那么我们今天就来学习一下算法中最基础的几种排序算法:

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 希尔排序
  5. 快速排序
  6. 归并排序
  7. 基数排序
  8. 堆排序

冒泡排序

算法思想:

顾名思义,冒泡排序的精髓在于【冒泡】,我们想象一下,水底的气泡从诞生到浮出水面的过程,这个过程为:气泡诞生-气泡上浮-浮出水面破灭,那么我们在计算机语言中,就可以根据气泡的上浮原理:

诞生:确定气泡的位置——选定第一个数的位置;

上浮:将大气泡上浮——数字挨个与后移路径中的每一个数字比较大小并互换位置;

浮出水面破灭:将破灭的气泡放置最后——将比较完后的数字放置最后,暂时抛弃;

诞生2:选择第二个气泡——继续选择第一个数的位置......

......      循环直到池里的气泡都选择完毕。

浅谈排序算法(上)

冒泡排序动画演示

那么我们用Java的代码可以这样表述,另外,针对排序做了进一步的优化

public static void maopaoSort(int[] arr){
    long start = new Date().getTime();
    boolean isSort = true;//设定一个布尔值用于判断剩下的数字是否有序,默认为True
    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]){
                isSort = false;//一旦进入次区间说明剩下的数字是无序的,仍需继续排序。
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        // 如果在某一次冒泡排序中没有交换顺序,说明该数组已经有序
        if (isSort){
            break;
        }
    }
    long end = new Date().getTime();

    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

 优点:比较简单,空间复杂度较低,是稳定的;

 缺点:时间复杂度太高,效率慢;

 

选择排序

算法思想:
1.在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
2.从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
3.以此类推,直到所有元素均排序完毕;

浅谈排序算法(上)

选择排序图示动画

 

用Java演示代码如下

public static void selectSort(int[] arr){
    long start = new Date().getTime();
    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i]; // 默认当前位置的数为最小
        int minindex = i; // 记录当前的位置坐标
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minindex = j;
            }
        }
        if (i != minindex){
            arr[minindex] = arr[i];
            arr[i] = min;
        }
    }
    long end = new Date().getTime();
    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

优点:一轮比较只需要换一次位置;

缺点:效率慢,不稳定。

 

插入排序

算法思想:

顾名思义,采用插入的方式,对无序数列进行排序。

可将其与抓牌比较,将新抓起的牌放入右手,并在左手按顺序比较,最后在合适的位置插入右手中的牌。

维护一个有序区,将数据一个一个插入到有序区的适当位置,直到整个数组都有序。即每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

浅谈排序算法(上)

插入排序动画演示

 

用Java实现插入排序算法

public static void insertSort(int[] arr){
    long start = new Date().getTime();
    for (int i = 1; i < arr.length; i++) {
        int insertIndex = i;
        int insertVal = arr[i];
        while (insertIndex > 0 && insertVal < arr[insertIndex - 1]){
            arr[insertIndex] = arr[insertIndex - 1];
            insertIndex--;
        }
        arr[insertIndex] = insertVal;
    }
    long end = new Date().getTime();
    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

优点:在运行次数少的情况下比较有优势,稳定;

缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候。


版权声明:peterx 发表于 2021年3月4日 下午1:52。
转载请注明:浅谈排序算法(上) | PM HOME

相关文章

暂无评论

暂无评论...