交换式排序法--快速排序法

快速排序(QuickSorting)是对冒泡排序的一种改进，由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

[Java] 纯文本查看 复制代码

//快速排序法[Demo135.java]排序1亿数据用时14秒
public class Demo135{
	public static void main(String []args){
		int arr[]={-1,-5,6,2,0,9,-3,-8,12,7};
		QuickSort qs=new QuickSort();
		qs.sort(0, arr.length-1, arr);
		//输出最后结果
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+"\t");
		}
	}
}
class QuickSort{
	public void sort(int left,int right,int [] arr){
		int l=left;
		int r=right;
		int pivot=arr[(left+right)/2];//找中间值
		int temp=0;
		while(l<r){
			while(arr[l]<pivot) l++;
			while(arr[r]>pivot) r--;
			if(l>=r) break;
			temp=arr[l];
			arr[l]=arr[r];
			arr[r]=temp;
			if(arr[l]==pivot) --r;
			if(arr[r]==pivot) ++l;
		}
		if(l==r){
			l++;
			r--;
		}
		if(left<r) sort(left,r,arr);
		if(right>l) sort(l,right,arr);
	}
}

                              

{:8_522:}有图好评！赞

很厉害的样子，刚开始学，还在努力中

有图好评！赞

package com.lin.quicksort;

import java.util.Arrays;
import com.lin.dao.SortService;

public class QuickSort
{
        public static void main(String[] args)
        {
                int[] arr = SortService.getArr(1000000, 100);
                quick(arr, 0, arr.length - 1);
                System.out.println(Arrays.toString(arr));
        }

        public static int sort(int[] arr, int left, int right)
        {
                if (arr == null || arr.length <= 0)
                {
                        return -1;
                }

                if (left < 0 || right < 0 || left > right)
                {
                        return -1;
                }

                /*
                 * [14, 44, 60, 82, 76, 4, 82, 97] 第一个作为 标准 midVal = 14 把14拿出来
                 * [NULL, 44, 60, 82, 76, 4, 82, 97] 先从右边开始 把小于 14 的值 4 将null变为4
                 * [4, 44, 60, 82, 76, 【4】, 82, 97] 右边的【4】就无意义可以替换 再从左边拿大于14的值 44 替换 4
                 * [4, 【44】, 60, 82, 76, 44, 82, 97] 左边【44】无效可以替换 最终左右下标会相同定位于【44】
                 * [4, 【44】, 60, 82, 76, 44, 82, 97] 【44】无意义可以替换为 标准【中轴】 返回下标 left或right
                 */
                int midVal = arr[left];
                while (left < right)
                {
                        // left<right防止 right==1时 --造成下标越界
                        // 或 left== ++时最大值越界
                        while (arr[right] >= midVal && left < right)
                        {
                                right--;
                        }
                        arr[left] = arr[right];
                        // = 等于是为了防止 arr[left]==arr[right]变成死循环
                        while (arr[left] <= midVal && left < right)
                        {
                                left++;
                        }
                        arr[right] = arr[left];
                }
                // 最后left==right
                arr[right] = midVal;
                return right;
        }

        public static void quick(int[] arr, int begin, int end)
        {
                if (begin >= end)
                {
                        return;
                }
                int temp = sort(arr, begin, end);
                quick(arr, begin, temp-1);
                quick(arr, temp+1, end);
        }
}