Java实现快速排序经典代码和算法思路

Java技术 潘老师 3个月前 (11-11) 77 ℃ (0) 扫码查看

本文重点讲解Java实现快速排序经典代码和算法思路。

快速排序的基本思想

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一 部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序 过程可以递归进行,以此达到整个数据变成有序序列。

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素,称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

切分原理

把一个数组切分成两个子数组的基本思想:

  • 1.找一个基准值,用两个指针分别指向数组的头部和尾部;
  • 2.先从尾部向头部开始搜索一个比基准值小或等于的元素,搜索到即停止,并记录指针的位置;
  • 3.再从头部向尾部开始搜索一个比基准值大或等于的元素,搜索到即停止,并记录指针的位置;
  • 4.交换当前左边指针位置和右边指针位置的元素;
  • 5.重复2,3,4步骤,直到左边指针的值大于右边指针的值停止。

快速排序图解

快速排序图解

快速排序Java代码实现

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};

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

        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }

    /**
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }

        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];

        //从左右两边交替扫描,直到left = right
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描,找到第一个比基准值小的元素
                right--;
            }

            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];

            while (left < right && arr[left] <= key) {
                //从左往右扫描,找到第一个比基准值大的元素
                left++;
            }

            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
}

快速排序的另一种实现,似乎更容易理解:

public static void QuickSort(int []arr,int low,int high) {
        if(low<high) {
            int pivotpos=partition(arr,low,high);
            QuickSort(arr,low,pivotpos-1);
            QuickSort(arr,pivotpos+1,high);
        }
    }
 
    private static int partition(int[] arr, int low, int high) {
         int pivot=arr[low];
         while(low<high) {
             //起初,一定要从右边指针开始,因为arr[low]的值已经扔给了pivot,arr[low]
             //想象成无数字的空位
             while(low<high&&pivot<=arr[high]) {
                 --high;
             }
             
             //把比pivot的小的数扔到左边指针
             //把arr[high]扔到arr[low]这个空位上
             //然后,high位置可以想象成无数字的空位
             arr[low]=arr[high];
             
             while(low<high&&arr[low]<=pivot) {
                 ++low;
             }
             //把比pivot大的数扔到右边
            //把arr[low]扔到arr[high]这个空位上
            //然后,low位置可以想象成是无数字的空位
             arr[high]=arr[low];
         }
         //此时low==high,return high也一样
         arr[low]=pivot;
        return low;
    }
}

 总结

以上就是Java实现快速排序经典代码和算法思路的全部内容了,希望对你有帮助!


版权声明:本站文章,如无说明,均为本站原创,转载请注明文章来源。如有侵权,请联系博主删除。
本文链接:https://www.panziye.com/java/11049.html
喜欢 (0)
请潘老师喝杯Coffee吧!】
分享 (0)
用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi,您需要填写昵称和邮箱!

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】