java之快速排序

/*快速排序 算法思路: 1、在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准,称为基准记录; 2、定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”...
/*快速排序
    算法思路:
        1、在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准,称为基准记录;
        2、定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”,key 表示“基准值”;
        3、首先,尾索引向前扫描,直到找到比基准值小的记录(left != righ),并替换首索引对应的值;
        4、然后,首索引向后扫描,直到找到比基准值大于的记录(left != righ),并替换尾索引对应的值;
        5、若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引所对应的值;
        6、再进行下一趟排序时,待排序列被分成两个区:[0,left-1],[righ+1,end]
        7、对每一个分区重复步骤2~6,直到所有分区中的记录都有序,排序成功。
*/
public class ArraysTest2 {

    public static void main(String[] args) {

        int[] arr = new int[]{-1,3,-2,5,8};
        System.out.print("快速排序前结果为:"+"n");
        for (int i : arr ) {
            System.out.print(i + "t");
        }
        quickSort(arr, 0, arr.length - 1);
        System.out.print("n"+"快速排序后结果为:"+"n");
        for (int i : arr ) {
            System.out.print(i + "t");
        }
    }

    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 (left < right && 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);
    }

}
  • 发表于 2020-07-30 20:00
  • 阅读 ( 93 )
  • 分类:网络文章

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除