Java算法基础之快速排序算法详解编程语言

所谓的快速排序的思想就是,首先把数组的第一个数拿出来作为一个key,在前后分别设置一个i,j作为标识,然后拿这个数组从后面往前遍历,
及j- -,直到找到第一个小于这个key的那个数然后交换这两个值,交换完成后,我们拿着这个key要从i往后遍历了,及i++ 一直循环到i=j结束,
当结束后,我们会发现大于这个key的值都会跑到这个key的后面,小于这个key的值就会跑到这个值的前面,然后我们对这个分段的数组再进行
递归调用就可以完成这个数组的排序。

public class QuickSort{ 
    public static void main(String[] args) { 
        int a[] = { 6, 2, 7, 5, 8, 1, 9, 3, 4 }; 
        quickSort(a, 0, a.length - 1); 
 
        System.out.println("排序后"); 
        for (int k = 0; k < a.length; k++) { 
            System.out.print(a[k] + " "); 
        } 
        System.out.println(); 
    } 
 
    public static void quickSort(int a[], int start, int end) { 
        int i, j; 
        i = start; 
        j = end; 
        if (a == null || a.length == 0) { 
            return; 
        } 
 
        while (i < j) { 
            while (i < j && a[i] <= a[j]) { 
                j--; // 右侧扫描 
            } 
            if (i < j) { // 找出第一个比key小的 交换位置 
                int temp = a[j]; 
                a[j] = a[i]; 
                a[i] = temp; 
            } 
 
            while (i < j && a[i] < a[j]) { 
                i++;// 左侧扫描(此时a[j]中存储着key值) 
            } 
            if (i < j) { // 找出第一个比key大的,交换位置 
                int temp = a[j]; 
                a[j] = a[i]; 
                a[i] = temp; 
            } 
 
            if (i - start > 1) { // 递归调用,把key前面的完成排序 
                quickSort(a, 0, i - 1); 
            } 
            if (end - j > 1) { 
                quickSort(a, j + 1, end); // 递归调用,把key后面的完成排序 
            } 
        } 
    } 
}

作者:blog.ytso.com

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/14277.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论