Jimmy小站

小明也有大梦想 — 蒋明/铭
当前位置:网站首页 / 数据结构算法 / 正文

小明学排序-快速排序

2016-03-23 / 数据结构算法 / 2371 次围观 / 0 次吐槽

快速排序法,原则是首先选中一个元素作为参考元。

一般选择首元素或中间元素等。

本代码使用首元素。

令下标 i , j 分别从头尾分别向中间靠拢,直到 i = j 时停止,

将左边大于参考元素的值的元素换到右边,

同理右边按照要求换到左边,完成一层迭代。

接下来以 下标 i (此时 i = j)作为分割点,分成左右两组。

再分别迭代进行快速排序。

package net.jimmyme;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        
        int[] source = {101,8,9,13,45,17,26,99,78,11,46,999,111};
        
        quickSort(source,0,source.length-1);
        System.out.println(Arrays.toString(source));
    }
    public static void quickSort(int[] source, int left, int right){
        
        int i = left;
        int j = right;
        int key = source[left];
        while (i < j) {
            while (i < j && source[j] >= key) {
                j--;
            }
            if (i < j) {
                source[i] = source[j];
                i++;
            }
            // 此时 j 下标的值 < key ,如果下标没有越界,换到左边去(source[i] 保存)
            // 最开始的source[i]保存在key 中,接下来的source[i]保存在前一轮的source[j]中
            // source[j] 保存在前一轮的source[i]中
            while (i < j && source[i] <= key) {
                i++;
            }
            if (i < j) {
                source[j] = source[i];
                j--;
            }
        }
        
        // 此时,i = j
        source[i] = key;
        
        if (left < i && left >=0) {
            quickSort(source, left, i-1);
        }
        if (j < right && j >= 0) {
            quickSort(source, j+1, right);
        }

    }

}


推荐您阅读更多有关于“排序算法Java,”的文章

[一个Java程序猿的转型之路,读研深造,专注机器学习推荐算法]
本站所有文章如无特别注明均为原创。作者:吉米酱 ,复制或转载请以超链接形式注明转自 Jimmy小站
原文地址《小明学排序-快速排序
额 本文暂时没人评论 来添加一个吧

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996