Java教程

算法-交换排序算法之快速排序

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

交换排序

  • 交换排序算法描述:比较相邻两个元素大小,如果反序,则交换。
  • 交换排序算法有两种:冒泡排序和快速排序

快速排序

算法描述

快速排序在数据序列中选择一个元素做为基准值(一般会选择第一个元素或最后一个元素),每趟从数据序列的两端开始交替进行,将小于基准值的元素交换到序列前端,将大于基准值的元素交换到序列的后端,介于两者之间的位置则成为基准值的最终位置。同时,序列被划为两个子序列,在分别对了个子序列进行快速排序,直到子序列的长度为1,则完成排序。

算法思路

image

算法实现

public static void quickSort(int[] arr, int begin, int end) {
    // 序列有效
    if (begin >= 0 && begin < end && end < arr.length) {
        int i = begin, j = end;  // begin 为左边最开始的元素的下标;end 为最后一个元素的下标
        int x = arr[i]; // 以第一个的元素为基准

        while (i != j) { // 当交叉比较时 左边和右边下标发生重合子运行结束
            while (i < j && arr[j] >= x) { // 从右边向前寻找较小的值移动,不移动与基准值相等的元素
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];  // 子序列的后端较小元素向前移动
            }
            while (i < j && arr[i] <= x) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i]; // 子序列前端较大的元素向后移动
            }
        }
        arr[i] = x; // 将基准值放入最终位置
        quickSort(arr, begin, j - 1); // 前端子序列再排序,递归调用
        quickSort(arr, i + 1, end); // 后端子序列在排序,递归调用
    }
}
这篇关于算法-交换排序算法之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!