黑马程序员技术交流社区

标题: Java学习之快速排序 [打印本页]

---

作者: yuzt    时间: 2016-11-1 16:43
标题: Java学习之快速排序

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

快速排序(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+"\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);

        }

}

                              

捕获.PNG (87.83 KB, 下载次数: 9)

下载附件

2016-11-1 16:42 上传

---

作者: leojr    时间: 2016-11-1 16:45
{:8_522:}有图好评！赞

---

作者: 默默默默    时间: 2016-11-1 17:28
很厉害的样子，刚开始学，还在努力中

---

作者: xbs783    时间: 2016-11-1 20:20
有图好评！赞

---

作者: 15626187339    时间: 2016-11-1 22:15
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);
        }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2