Java教程

常见排序算法

本文主要是介绍常见排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

这些基础的算法真是容易忘,一段时间不写细节就不会处理了。在此记录一下。

1、初级的桶排序

如需要对10以内的数进行排序,可以先初始化一个长度为10的数组。然后遍历,遍历到哪个数就将数组对应的下标加1,如遍历到3,则a[3]++。整个遍历结束后,再通过输出数组即可得到有序数据。需要注意的是,a[i]是多少则需要打印多少次。
这种算法相当于是用下标记录数据,用值记录次数。

该算法的优点是快速,其时间复杂度是O(n)。但是该算法的缺点是占用过多的空间,如果需要对10000个数排序,那么需要申请长度10000数组来存储,相当于用空间换时间。

参考代码如下:

/**
 * 简单的桶排序(实际的桶排序要比这个复杂)
 * @param a 待排序的数组
 */
public static void bucketSort(int[] a) {
    // 先定义桶
    int[] tong = new int[10];      // 假设a数组存放的是10以内的数据,故需要定义10个桶
    for (int i = 0; i < tong.length; i++) {
        tong[i] = 0;   // 初始化桶中的每一位数 (假设待排序的数中不存在-1)
    }

    // 遍历待排数据,将数据放入到相应的桶中
    for (int i = 0; i < a.length; i++) {
        tong[a[i]]++;
    }

    // 输出桶中的数据,即已经排序好的数据
    for (int i = 0; i < tong.length; i++) {
        // 只打印存放了数据的桶
        if (tong[i] != 0) {
            for (int j = 0; j < tong[i]; j++) {
                // 在某个桶的位置上重复了几次,那么就打印多少次
                System.out.print(i + ",");
            }
        }
    }
}

2、冒泡排序

冒泡排序的思想是通过依次比较相邻的两个数的,如果顺序不对,则进行调换。在每一真趟的的冒泡的过程中,只能将一个数归位。在对n个数排序中,只需将n-1归位即可。故排序n个的数只需要n-1趟。该算法的优点是理解及实现难度不在,但是时间复杂度为O(n2)。

参考代码如下:

/**
 * 冒泡排序
 * @param a
 */
public static void bubbleSort(int[] a) {
    // 将一个元素依次与其他元素比较,冒泡到最后为一趟
    // n个元素只需要将n - 1个数归位,即需要n - 1趟

    int count = a.length - 1;   // 需要比较的次数
    for (int i = 1; i <= count; i++) {

        boolean hasSwap = false;    // 当前趟有没有发生交换,这样可以优化一下冒泡排序算法。

        // 第i趟时,只需比较count-i+1次,因为乘余的数已经排好序了。
        for (int j = 0; j <= count - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = tmp;
                hasSwap = true;
            }
        }

        // 如果没有发生过交换,则说明已经排好序了
        if (!hasSwap) {
            System.out.println("第" + i + "趟排序已经排好的,结束排序");
            break;
        }
    }

    /**
     * 冒泡时间复杂度推导:
     * 第一趟要迭代 n - 1次
     * 第二趟      n - 2次
     *
     *
     * 第n-1趟,   1次
     * 累积求和即是 (n - 1) + (n - 2) + (n - 3) + ..... + 1;
     * n (n - 1) / 2
     * 故时间复杂度是: O(n2)
     */
}

3、快速排序

快速排序是一种基于二分的思想。由于其比较是跳跃式的,故比冒泡排序要快很多,但是最差的情况下等同于冒泡排序。

参考代码如下:

/**
 * 快速排序
 *
 * @param a
 * @param left 排序的范围 左起点
 * @param right 右起点
 */
public static void quickSort(int[] a, int left, int right) {
    // 递归停止条件
    if (left > right) {
        return;
    }

    int i = left;
    int j = right;
    int temp = a[left];    // 选定第一个元素为基准元素

    while (i < j) {
        // 因为基准元素是最左边的,故首先要从最右边开始找到一个比基准元素小的元素,j为其索引。顺序很重要。同时这里是a[j] >= temp,不能掉了等号。
        while (a[j] >= temp && i < j) {
            j--;
        }

        // 从左边开始找到一个比基准元素大的元素,i为其索引
        while (a[i] <= temp && i < j) {
            i++;
        }

        // 当i与j没有相遇时才交换,相遇时则表明此次基准数已经归位
        if (i < j) {
            // 交换i和j的位置
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    // i 与 j 相遇后将基准元素与i处的互换
    a[left] = a[i];
    a[i] = temp;

    // 将基准元素左边的排序
    quickSort(a, left, i - 1);
    // 同上,将基准元素右边的排序
    quickSort(a, j + 1, right);
}

4、插入排序

for (int i = 0; i < nums.length; i++) {
	// 当前值与前一个相比, 始终记住这个。 
    int j = i - 1;
    int tmp = nums[i];

    while (j >= 0 && tmp < nums[j]) {
    	// j往后挪动,因为j + 1 = i,当前值已经保存在tmp了,故无需担心nums[j + 1]的值被覆盖。 
        nums[j + 1] = nums[j];
        j--;
    }
	
	// 找到相应的位置挺好入
    nums[j + 1] = tmp;
}

5、Shell排序

fun shellSort(a: IntArray) {

        var size = a.size
        var gap = size / 2     // 初始gap为数组长度的一半
        while (gap > 0) {

            // 如下代码的思想为插入排序思想
            for (i in gap until size) {
                var tmp = a[i]
                var j = i - gap // 如果此时j小于0,则会跳过while循环。a[j+gap]即为a[i]
                while (j >= 0 && a[j] > tmp) {
                    a[j + gap] = a[j]
                    j -= gap
                }
                a[j + gap] = tmp
            }

            gap /= 2    // gap每次减半
        }
    }
这篇关于常见排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!