算法-快速排序算法

算法说明

在待排序的元素任取一个元素作为基准(通常选第一个元素,称为基准元素)
将待排序的元素进行分块,比基准元素大的元素移动到基准元素的右侧;
比基准元素小的移动到作左侧,从而一趟排序过程,就可以锁定基准元素的最终位置。
对左右两个分块重复以上步骤直到所有元素都是有序的(递归过程)

代码示例

// 快速排序
public static void quickSort(int[] array, int start, int end) {
    int tmp = 0;
    // 退出条件
    if(start >= end) {
        return ;
    }
    // 设置基准值
    int key = array[start];
    int start_bak = start;
    int end_bak = end;
    while(start_bak < end_bak) {
        // 右边发现小于key的值时,停止循环
        while(array[end_bak] >= key && start_bak < end_bak) {
            end_bak--;
        }
        // 这里一定时右边开始,上下两个循环不能调换
        // 左边发现大于key的值时,停止循环
        while(array[start_bak] <= key && start_bak < end_bak) {
            start_bak++;
        }
        // 交换数据
        tmp = array[end_bak];
        array[end_bak] = array[start_bak];
        array[start_bak] = tmp;
    }
    // 确定基准值位置
    array[start] = array[start_bak];
    array[start_bak] = key;
    // 分别左右快速排序
    quickSort(array, start, end_bak - 1);
    quickSort(array, end_bak + 1, end);
}
// 快速排序入口
public static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
}

调用示例:

public static void main(String[] args) {
    int[] array = {8, 9, 2, 0, 5, 2, 22, 39, -3,234, 10, 33};
    quickSort(array);
    for(int i : array) {
        System.out.println(i);
    }
}

时间复杂度

一趟快速排序,我们只确定了一个元素的最终位置;
我们最终需要经过n趟快速排序才能将一个含有N个数据元素的序列排好序。
最好情况下,每一次划分都正好将数组分成长度相等的两半O(NlogN)。
最坏情况下,每一次划分都将数组分成了0和n-1两部分: O(N^2)。

上一篇:Java-实现文件sha1编码获取


下一篇:Maven项目配置logback