美文网首页
快速排序算法

快速排序算法

作者: K29 | 来源:发表于2017-03-12 08:59 被阅读0次

介绍:
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。
步骤:
从数列中挑出一个元素,称为 “基准”(pivot),重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

public void _quick_sort(int[] arrays, int start, int end) {
//        int[] a = {49, 58, 65, 12, 45, 5};
        if (start >= end) {
            return;
        }
        int i = start;
        int j = end;
        int value = arrays[i];
        boolean flag = true;
        while (i != j) {
            if (flag) {
                if (value > arrays[j]) {
                    swap(arrays, i, j);
                    flag = false;
                } else {
                    j--;
                }
            } else {
                if (value < arrays[i]) {
                    swap(arrays, i, j);
                    flag = true;
                } else {
                    i++;
                }
            }
        }
             /*递归调用,把key前面的完成排序*/
        this._quick_sort(arrays, start, i - 1);

        /*递归调用,把key后面的完成排序*/
        this._quick_sort(arrays, j + 1, end);
    }


  public static void main(String[] args) {

        int a[] = {8, 6, 4, 7, 9, 3, 25, 5, 1};

        _quick_sort(a, 0, a.length-1);

        for(int x = 0;x<a.length;x++){
            System.out.print(a[x]+" ");
        }
    }

相关文章

网友评论

      本文标题:快速排序算法

      本文链接:https://www.haomeiwen.com/subject/voltnttx.html