Java算法基础之快速排序算法

青旅半醒 2022-07-12 08:24 179阅读 0赞

所谓的快速排序的思想就是，首先把数组的第一个数拿出来作为一个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后面的完成排序
                }
            }
        }
    }

作者：[itmyhome][]

[itmyhome]: http://blog.csdn.net/itmyhome1990