@IT·互联网程序员

3.一步一步分解快排

2016-08-06  本文已影响325人  KaelQ

1.原理

Quick Sort 属于交换排序,是对冒泡算法进行的改造。

基本原理:分治法和填坑法

2.java写法

private static int partition(int a[], int i, int j) {
        int key = a[i];//key值
        while (i < j) {
            while (i < j && a[j] > key)// 从右向左小循环
                j--;
            if (a[j] <= key)//判定填充
                a[i] = a[j];
            while (i < j && a[i] < key)// 从左向右小循环
                i++;
            if (a[i] >= key)//判定填充
                a[j] = a[i];
        }
        a[i] = key;// 把轴元素放在轴所在地位置
        return i;// 返回轴所在的位置
    }

实现递归的quicksort():

private void quickSort(int data[], int low, int high) {// 递归
        int q;
        if (low < high) {
            q = partition(data, low, high);
            quickSort(data, q + 1, high);//对q左边进行分类
            quickSort(data, low, q - 1);//对q右边进行分类
        }
    }

3.时间复杂度

上一篇下一篇

猜你喜欢

热点阅读