黑马程序员技术交流社区

标题: 【西安校区】冒泡排序和快速排序 [打印本页]

作者: 逆风TO    时间: 2020-3-4 10:13
标题: 【西安校区】冒泡排序和快速排序
概述
Java中排序算法是非常重要的一部分,这里简单分析下冒泡排序和快速排序的实现思路及其代码实现。

常见排序算法时间复杂度表
排序法        平均时间复杂度        最差情形        稳定度        额外空间        备注
冒泡排序        O(n^2)        O(n^2)        稳定        O(1)        n小时较好
选择排序        O(n^2)        O(n^2)        不稳定        O(1)        n小时较好
插入排序        O(n^2)        O(n^2)        稳定        O(1)        大部分已排序较好
快速排序        O(nlogn)        O(n^2)        不稳定        O(nlogn)        n大时较好
shell排序        O(nlogn)        O(n^s)1<s<2        不稳定        O(1)        s是所选分组
归并排序        O(nlogn)        O(nlogn)        稳定        O(1)        n大时较好
堆排序        O(nlogn)        O(nlogn)        稳定        O(1)        n大时较好
基数排序        O(logrB)        O(logrB)        稳定        O(n)        B为真数(0-9),r为基数(个十百)
冒泡排序(从小到大排序)
冒泡排序(Bubble Sorting)的基本思想:从数组的左端开始遍历,依次比较前后相邻的两个元素,如果发现前一个元素比后一个元素大则进行交换,使得值大的向数组的右端移动,值小的向数组的左端移动。

有时候我们在冒泡过程中已经有序,不会进行交换,所以可以设置一个flag标记位,判断本次遍历是否进行了交换,如果没有进行交换则说明该数组已经是一个有序的数组了,可以退出循环。

冒泡排序图解

代码实现
[Java] 纯文本查看 复制代码
public class BubbleSort {

        public static void bubbleSort(int[] array) {
                if (array == null || array.length <= 0) {
                        throw new IllegalArgumentException();
                }
               
                int temp = 0;
                boolean flag = false;
                for (int i = 0;i < array.length - 1;i++) {
                        for (int j = 0; j < array.length - i - 1;j++) {
                                if (array[j] > array[j + 1]) {
                                        temp = array[j];
                                        array[j] = array[j + 1];
                                        array[j + 1] = temp;
                                        flag = true;
                                }
                        }
                        if (flag == false) {
                                break;
                        } else {
                                flag = true;
                        }
                }
        }
       
}


快速排序(从小到大)

快速排序的思想:在数组中选一个数作为基准,将比这个基准大的数移动到它的右边,将比这个基准小的数移动到左边,然后通过递归的方式最后达到有序的状态。

代码实现
[Java] 纯文本查看 复制代码
public class QuickSort {

        public static void main(String[] args) {
        int[] array = {69,62,89,37,97,17,28,49,-1};

        quickSort(array,0,array.length-1);

        System.out.println(Arrays.toString(array));
    }
        public static void quickSort(int[] arr, int left, int right) {
                if (arr == null || arr.length <= 0) {
                        throw new IllegalArgumentException();
                }
                int l = left;
                int r = right;
                // 我选择的是以中间值作为基准进行排序
                int pivot = arr[(l + r)/2];
                int temp = 0;
                while (l < r) {
                        // 在基准的左边挑选出比它大的元素
                        while (arr[l] < pivot) {
                                l++;
                        }
                        // 在基准的右边挑选出比它小的数
                        while (arr[r] > pivot) {
                                r--;
                        }
                        // 当两个指针找到一块,则退出循环
                        if (l >= r) {
                                break;
                        }
                        // 将挑出的两个值进行交换
                        temp = arr[l];
                        arr[l] = arr[r];
                        arr[r] = temp;
                       
                        // 左指针值等于中间值时,说明在上一步循环中基准的左边都是比它小的数,是等于pivot才退出循环的
                        if (arr[l] == pivot) {
                                r--;
                        }
                       
                        // 右指针值等于中间值时,说明在上一步循环中基准的右边都是比它大的数,是等于pivot才退出循环的
                        if (arr[r] == pivot) {
                                l++;
                        }
                }

                if (l == r) {
                        l++;
                        r--;
                }
               
                // 向左递归
                if (left < r) {
                        quickSort(arr, left, r);
                }
       
                if (right > l) {
                        quickSort(arr, l, right);
                }
        }
}








欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2