核心思想: 选取一个枢轴 pivot, 将比它小的放到它左边, 将比它大的放到它右侧, 返回 pivot 的位置, 将数列分成两段进行递归调用.
- package QuickSort;
- public class QuickSort {
- private int[] b=new int[10]; // 存 9 个数, 从 1-9
- private int size;
- // 初始化
- public QuickSort(int[] a)
- {
- for(int i=0;i<a.length;i++)
- {
- this.b[i+1]=a[i];
- }
- size=a.length;
- }
- // 遍历
- public void traversal()
- {
- for(int i=1;i<=size;i++)
- {
- System.out.println(b[i]);
- }
- }
- public void Qsort(int low,int high)
- {
- int pivot;
- if(low<high)
- {
- pivot=Partition(low, high);
- Qsort(low, pivot-1); // 递归
- Qsort(pivot+1, high);// 递归
- }
- }
- public void swap(int[] temp,int a,int b)
- {
- temp[a]=temp[a]+temp[b];
- temp[b]=temp[a]-temp[b];
- temp[a]=temp[a]-temp[b];
- }
- public int Partition(int low,int high)
- {
- int pivotkey; // 枢轴
- pivotkey=b[low]; // 用表的第一个数当枢轴
- while(low<high)
- {
- while((low<high)&&(b[high]>=pivotkey)) // 将比枢轴小的数换到左边
- {
- high--;
- }
- swap(b, low, high);
- while((low<high)&&(b[low]<=pivotkey)) // 将比枢轴小的数换到右边
- {
- low++;
- }
- swap(b, low, high);
- }
- b[low]=pivotkey;
- return low;
- }
- }
测试:
- package QuickSort;
- public class App {
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- int a[]={50,10,90,30,70,40,80,60,20};
- QuickSort sort=new QuickSort(a);
- sort.Qsort(1, 9);
- sort.traversal();
- }
- }
结果:
- 10
- 20
- 30
- 40
- 50
- 60
- 70
- 80
- 90
快速排序
来源: http://www.bubuko.com/infodetail-2905458.html