专栏首页weixuqin 的专栏排序算法的简单实现(冒泡和快排)

排序算法的简单实现(冒泡和快排)

排序算法

冒泡排序

原理:把相邻的元素两两比较,根据大小来交换元素的位置。

原始的冒泡排序是稳定排序。由于该排序的每一轮要遍历所以元素,轮转的次数和元素数量相当,所以时间复杂度是 O(N^2)。

java代码表达如下:

import java.util.Arrays;

public class BubbleSort{
    private static void sort(int array[]){
        int tmp = 0;
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array.length - i - 1;j++) {
                if (array[j] > array[j+1]) {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{5,8,6,3,9,2,1,7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

(使用双循环来进行排序。外部循环控制所有的回合,内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。)

冒泡优化(一)

判断出数列已经有序,并且做出标记,剩下的几轮排序就可以不必执行,提早结束工作。

代码如下:

import java.util.Arrays;

public class BubbleSort{
    private static void sort(int arrray[]){
        int tmp = 0;
        for (int i = 0; i < arrray.length; i++) {
            //有序标记,每一轮的初始是true
            boolean isSorted = true;
            for (int j = 0; j < arrray.length - i - 1; j++ ) {
                if(arrray[j] > arrray[j+1]) {
                    tmp = arrray[j];
                    arrray[j] = arrray[j+1];
                    arrray[j+1] = tmp;

                    //有元素交换,所以不是有序,标记变为false
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }
        }
    }

    public static void main(String[] args){
        int[] arrray = new int[]{5,8,6,3,9,2,1,7};
        sort(arrray);
        System.out.println(Arrays.toString(arrray));
    }
}

利用布尔变量 isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。

冒泡优化(二)

如果元素排序前面无序,后面无序,我们可以设定排序边界,这样当遍历到有序数组时,跳出循环,结束程序。

思路:我们在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。

代码如下:

import java.util.Arrays;

public class BubbleSort {
    private static void sort(int array[]) {
        int tmp = 0;
        // 记录最后一次交换的位置
        int lastExchangeIndex = 0;
        // 无序数列的边界,每次比较只需要比到这里为止
        int sortBorder = array.length - 1;
        for (int i = 0; i < array.length; i++) {
            // 有序标记,每一轮的初始是true
            boolean isSorted = true;
            for (int j = 0; j < sortBorder; j++) {
                if (array[j] > array[j+1]) {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    // 有元素交换,所以不是有序,标记为false
                    isSorted = false;
                    // 把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }

            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{3,4,2,1,5,6,7,8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

sortBorder 就是无序数列的边界。每一轮排序过程中,sortBorder 之后的元素就完全不需要比较了,肯定是有序的。

快速排序

快速排序跟冒泡排序一样,都属于交换类排序,通过采用不断的比较和移动元素来实现排序。

快速排序利用了 ”分治法“ 的思想, 通过设置基准数 key ,将比基准数大的数从前面移动到后面,比基准数小的数从后面移动到前面,将数组分为两部分,其中以 key 为中心, key 左边的数比 key 小,key 右边的数比 key 大,然后对这两部分分别重复这个排序的过程,直到整个有序。

由于采取 ”分治法“ ,我们可以很容易的得出快速排序的平均时间复杂度为:O(nlogn)

快速排序的简单实现:

import java.util.Arrays;

public class QuickSort {
    private static void quickSort(int[] a, int low, int high) {
        //1.找到递归算法的出口
        if (low > high) {
            return;
        }
        //2. 存
        int i = low;
        int j = high;
        //3. key
        int key = a[low];
        //4,完成一趟排序
        while(i < j) {
            //4.1 从右往左找到第一个小于key的数
            while(i<j && a[j] > key){
                j--;
            }
            //4.2 从左往右找到第一个大于key的数
            while (i<j && a[i] <= key) { 
                i++;
            }
            //4.3 交换
            if(i < j){
                int p = a[i];
                a[i] = a[j];
                a[j] = p;
            }
        }
        //4.4 调整key的位置
        int p = a[i];
        a[i] = a[low];
        a[low] = p;
        //5. 对key左边的数快排
        quickSort(a, low, i - 1);
        //6. 对key右边的数快排
        quickSort(a, i + 1, high);
    }

    public static void quickSort(int[] a){
        if (a.length>0) {
            quickSort(a, 0, a.length - 1);
        }
    }

    public static void main(String[] args) {
        int[] a = {1,2,4,5,7,4,5,3,9,0};
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • spring 学习(五):spring 事务

    一个数据库事务通常包含了一个序列的对数据库的读/写操作。它的存在包含有以下两个目的:

    希希里之海
  • Nginx 进行性能配置

      总所周知,网络上我们购买的服务器的性能各不相同,如果采用 Nginx 的默认配置的话,无法将服务器的全部性能优势发挥出来,我们应该选择适合自己需求的配置。

    希希里之海
  • Idea 使用 Junit4 进行单元测试

    Idea 默认使用 arquillian junit4 作为测试框架,我们将其更改为 Junit4。

    希希里之海
  • 漫画:最最最最最简单的选择排序

    当我们用到它的时候,数据规模越小越好,不会占用额外的内存空间并且运行时间与输入无关。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

    Python进击者
  • 总结5种比较高效常用的排序算法

    1 概述     本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性...

    闵开慧
  • 总结五种常见的排序算法

        本文对比较常用且比较高效的排序算法进行了总结和解析,并贴出了比较精简的实现代码,包括选择排序、插入排序、归并排序、希尔排序、快速排序等。算法性能比较如下...

    Kevin_Zhang
  • 二维数组中的查找

    在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该...

    用户3003813
  • 算法考试填数字问题

    forrestlin
  • Java 3:顺序表的操作

    顺序表常见操作有插入、删除、查找、修改。 一、插入: 1.插入有头插、尾插、任意位置插入。在插入时要注意下标的取值在顺序表长度范围内。所以最好在插入之前进行扩容...

    py3study
  • LeetCode 1122. 数组的相对排序

    arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券