• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

快速排序算法

算法 wangting 3年前 (2017-11-14) 657次浏览

快速排序算法

时间复杂度:O(n*lgn)
最坏:O(n^2)
空间复杂度:O(n*lgn)
不稳定。

快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)。
通常是用于排序的最佳选择。因为,基于比较的排序,最快也只能达到O(nlgn)。
快速排序和冒泡排序相似,都是通过多次比较和交换来实现排序

具体流程如下:

1、首先设定一个分界值,通过分界值将数组分成左右两部分,将大于等于分界值的数据交换集中到右侧数组,将小于分界值的数据交换集中到左侧数组;
2、然后,左侧数组和右侧数组可以独立排序。对于左侧数组可以取一个分界值,将左侧数组分成左右两个部分,同样将左边放置小于分界值的数据,右侧放置大于等于分界值的数据。对右侧数组做类似处理。
3、重复上述过程,其实就是递归。通过递归将左侧数组排好序后,再递归处理右侧数据。当左、右两部分数据都排好序后,整个数组的排序也就完成了。

假如有初始数据:25 11 45 26 12 78。
1、首先设定一个分界值,这里选择第一个元素—25。在变量left中保存数组的最小序号0,在变量right中保存数组的最大序号6,在变量base中保存分界值25。
2、从数组右侧开始,逐个与分界值25比较,直到找到小于base的数据为止。这里,12 就比分界值25小。
3、将右侧比分界值小的数据,保存到 A[left](A[0])元素中。
4、从数组左侧开始,逐个与分界值25比较,直到找到大于等于base的数据为止。这里,数组最左侧的数据为12,比分界值小,将left自增1,再取A[left](A[1])的值为45,因45大于25,结束查找。
5、将左侧比分界值大的数保存到A[right]元素中。
6、将分界值保存到A[left]中。经过一轮比较和交换,base数据左侧的数都是比base值小的数,右侧都是比base值大的数。
7、接下来,通过递归调用,将left左侧的数据进行同样的排序,再将left右侧的数据进行同样的排序。

快速排序对冒泡排序进行了改进,因此具有更好的执行效率。平均时间复杂度是O(nlogn)。

快速排序算法

代码实现如下:

[code lang=”java”]
/**
* 快速排序
*/
public class QuickSort implements ISort{</pre>
<pre>public void sort(int[] arr) {
quickSort(arr, 0, arr.length – 1);
}

private static void quickSort(int[] arr, int left, int right){
int t;
int ltemp = left;
int rtemp = right;
// 分界值
int fIndex = arr[(left + right)/ 2];
while(ltemp < rtemp) {
// 从左侧开始查找比分界值大的数
while(arr[ltemp] < fIndex) {
// 元素小于分界值,继续查找
++ltemp;
}
// 从右侧开始查找比分界值小的数
while(arr[rtemp] > fIndex) {
// 元素大于分界值,继续查找
–rtemp;
}
// 如果查到的比分界值大的数的下标小于等于比分界值小的数的下标,则进行交换
if(ltemp <= rtemp) {
t = arr[ltemp];
arr[ltemp] = arr[rtemp];
arr[rtemp] = t;
–rtemp;
++ltemp;
}
if(ltemp == rtemp) {
ltemp++;
}
System.out.println( Arrays.toString(arr));
if(left < rtemp) {
quickSort(arr, left, ltemp – 1);
}
if(ltemp < right) {
quickSort(arr, rtemp + 1, right);
}
}
}</pre>
<pre>} [/code]

public class QuickSort {

    public static void quickSort(int arr[],int _left,int _right){
        int left = _left;
        int right = _right;
        int temp = 0;
        if(left <= right){   //待排序的元素至少有两个的情况
            temp = arr[left];  //待排序的第一个元素作为基准元素
            while(left != right){   //从左右两边交替扫描,直到left = right
                while(right > left && arr[right] >= temp)  
                     right --;        //从右往左扫描,找到第一个比基准元素小的元素
                  arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换
                while(left < right && arr[left] <= temp)
                     left ++;         //从左往右扫描,找到第一个比基准元素大的元素
                  arr[right] = arr[left];  //找到这种元素arr[left]后,与arr[right]交换
            }
            arr[right] = temp;    //基准元素归位
            quickSort(arr,_left,left-1);  //对基准元素左边的元素进行递归排序
            quickSort(arr, right+1,_right);  //对基准元素右边的进行递归排序
        }        
    }
    public static void main(String[] args) {
        int array[] = {10,5,3,1,7,2,8};
        System.out.println("排序之前:");
        for(int element : array){
            System.out.print(element+" ");
        }
        
        quickSort(array,0,array.length-1);
        System.out.println("\n排序之后:");
        for(int element : array){
            System.out.print(element+" ");
        }

    }

}

程序员灯塔 , 版权所有
转载请注明原文链接:https://www.wangt.cc/2017/11/%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95/
喜欢 (0)