【数据结构与算法】快速排序

不念不忘少年蓝@ 2022-08-10 16:56 178阅读 0赞

*  空间复杂度

由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量与递归调用的最大深度一致。最好情况是O(log2(n+1))；最坏情况是O(n)；平均情况是O(log2n)。

*  时间复杂度

快速排序的运行时间与划分是否对称有关。最坏的情况是划分为0和n-1，时间复杂度是O(n^2)。最好的情况是均分，时间复杂度是O(n\*log2n)。平均情况与最好情况的运行时间很接近。

快速排序是内排序中平均性能最优的排序算法。

这里对快速排序的原理就不详细叙述了，这篇博客讲的非常好，[点击打开链接][Link 1]。

*  代码实现

/**
     * 源码名称：QuickSort.java 
     * 日期：2014-08-12 
     * 程序功能：快速排序 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    public class QuickSort {
    	public void quickSort(int[] in, int head, int tail) {
    		if (head >= tail) {
    			return;
    		} else {
    			int povit = quickPass(in, head, tail);
    			quickSort(in, head, povit - 1);
    			quickSort(in, povit + 1, tail);
    		}
    	}
    	/**
    	 * 函 数 名：quickPass 
    	 * 功能描述：单趟快速排序 
    	 * 输入参数：
    	 * @param in 待排序数组 
    	 * @param head 起点索引
    	 * @param tail 终点索引 
    	 */
    	public int quickPass(int[] in, int head, int tail) {
    		int left = head;
    		int right = tail;
    		int tmp = in[left];
    		while (left < right) {
    			while (left < right && in[right] >= tmp) {
    				right--;
    			}
    			if (left < right) {
    
    				in[left] = in[right];
    				left++;
    			}
    			while (left < right && in[left] <= tmp) {
    				left++;
    			}
    			if (left < right) {
    				in[right] = in[left];
    				right--;
    			}
    		}
    		in[left] = tmp;
    		return left;
    	}
    
    	public static void main(String[] args) {
    		int[] caseOne = { 6, 5, 4, 3, 2, 1, 10, 2 };
    		int[] caseTwo = { 1, 6, 5, 2, 4, 3 };
    		QuickSort mQuickSort = new QuickSort();
    		mQuickSort.quickSort(caseOne, 0, caseOne.length - 1);
    		for (int i : caseOne) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    		mQuickSort.quickSort(caseTwo, 0, caseTwo.length - 1);
    		for (int i : caseTwo) {
    			System.out.print(i + " ");
    		}
    	}
    }

[Link 1]: http://blog.csdn.net/morewindows/article/details/6684558