排序算法之快速排序
package com.lin.sort;/*** @author 作者 林尤庆* @version 创建时间：2016-8-12 下午02:42:05* 类说明 :快速排序法(Quick Sort)** 快速排序的最坏时间复杂度为O(n^2).* 快速排序所占用的辅助空间为递归时所需栈的深度，故空间复杂度为O（log2(n)）。同时，快速排序是不稳定的排序。*/public class QuickSort {public void swap(int a[],int i,int j){int temp=a[i];a[i]=a[j];a[j]=temp;}public int partSort(int a[],int low,int high){int pivot,p_pos,i;p_pos=low;pivot=a[p_pos];for(i=low+1;i<=high;i++){if(a[i]>pivot){p_pos++;swap(a, p_pos, i);}}swap(a, low, p_pos);return p_pos;}public void quicksort(int a[],int low,int high){int pivot;if(low<high){pivot=partSort(a, low, high);quicksort(a, low, pivot-1);quicksort(a, pivot+1, high);}}public static void main(String[] args) {// 快速排序法(Quick Sort)int vec[] = new int[] { 37, 46, 33, -5, 17, 51 };QuickSort s = new QuickSort();long begin = System.currentTimeMillis();for (int k = 0; k < vec.length; k++) {s.quicksort(vec, 0, vec.length-1);}long end = System.currentTimeMillis();System.out.println("快速法用时为：" + (end - begin));// 打印排序好的结果for (int i = 0; i < vec.length; i++) {System.out.print(vec[i]+" ");}}}
测试结果：
快速法用时为：051 46 37 33 17 -5
谁践踏了优雅
爱被打了一巴掌
系统管理员
还没有评论，来说两句吧...