精华内容
下载资源
问答
  • 快速排序 java实现

    2014-04-04 15:48:33
    快速排序 java实现
  • 快速排序java实现

    2021-02-28 18:52:49
    文章目录快速排序java实现使用步骤总结 快速排序java实现 假设一个数组 int i[] = {6,5,0,7,9,6,1,4,5,12,10,3,8,19}; 用快速排序法进行从小到大排序。 原理为寻找一个基准数,一般为第一个数。然后将这个数字取出...


    快速排序java实现

    假设一个数组 int i[] = {6,5,0,7,9,6,1,4,5,12,10,3,8,19};
    用快速排序法进行从小到大排序。
    原理为寻找一个基准数,一般为第一个数。然后将这个数字取出。从后往前寻找比它小的数,放到前面。这时又有了一个空位。在从前往后寻找比它大的数,放进之前的位置,不断重复。

    在这里插入图片描述


    使用步骤

    核心代码:

      int start = 0;
      int x = i[start];
      int end = i.length-1;
            while (start<end){
                while (start<end&&i[end]>x){
                    end--;
                }
                if(start<end){
                    i[start] = i[end];
                    start++;
                }
                while (start<end&&i[start]<x){
                    start++;
                }
                if(start<end){
                    i[end] = i[start];
                    end--;
                }
            }
            i[start]=x;
    

    运行一次之后:

    [3, 5, 0, 5, 4, 1, 6, 6, 9, 12, 10, 7, 8, 19]
    

    运行一次之后,用递归不断调用。
    完整实现代码:

            int i[] = {6,5,0,7,9,6,1,4,5,12,10,3,8,19};
            int start = 0;
            int end = i.length-1;
            quickSort(i,start,end);
            System.out.println(Arrays.toString(i));
        }
        public static void quickSort(int[] i,int start,int end){
            if(start<end){
                int middle = middles(i,start,end);
                quickSort(i,start,middle-1);
                quickSort(i,middle+1,end); 
            }
        }
        public static int middles(int[] i,int start,int end){
            int x = i[start];
            while (start<end){
                while (start<end&&i[end]>x){
                    end--;
                }
                if(start<end){
                    i[start] = i[end];
                    start++;
                }
                while (start<end&&i[start]<x){
                    start++;
                }
                if(start<end){
                    i[end] = i[start];
                    end--;
                }
            }
            i[start]=x;
            return start;
        }
    
    

    输出

    [0, 1, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 12, 19]
    

    总结

    快速排序在绝大部分时候优于冒泡排序。应当优先使用。

    展开全文
  • 快速排序Java实现

    2019-08-20 09:16:32
    快速排序Java实现 https://blog.csdn.net/YelloJesse/article/details/90730479

    快速排序Java实现

    https://blog.csdn.net/YelloJesse/article/details/90730479

    展开全文
  • 快速排序 Java 实现

    2020-04-12 21:44:35
    概念快速排序(Quicksort)是对冒泡排序的一种改进。参考:[数据结构与算法(Kotlin语言)]1.冒泡排序(Bubble Sort)快速排序是C.R.A.Hoare于196...

    概念

    快速排序(Quicksort)是对冒泡排序的一种改进。 

    参考: [数据结构与算法(Kotlin语言)]1.冒泡排序(Bubble Sort)

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    原理

    Quicksort 的基本思想是:把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置. 以后采用递归的方式分别对前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。

    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小;

    然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    快速排序具有最好的平均性能(average behavior),但最坏性能(worst case behavior)和插入排序相同,也是O(n^2)。比如一个序列5,4,3,2,1,要排为1,2,3,4,5。按照快速排序方法,每次只会有一个数据进入正确顺序,不能把数据分成大小相当的两份,很明显,排序的过程就成了一个歪脖子树,树的深度为n,那时间复杂度就成了O(n^2)。

    尽管如此,需要排序的情况几乎都是乱序的,自然性能就保证了。据书上的测试图来看,在数据量小于20的时候,插入排序具有最好的性能。当大于20时,快速排序具有最好的性能,归并(merge sort)和堆排序(heap sort)也望尘莫及,尽管复杂度都为nlog2(n)。

    1、算法思想

         快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    (1) 分治法的基本思想

         分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

    (2)快速排序的基本思想

         设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

    ①分解: 

         在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。

      注意:

         划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):

         R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

                      其中low≤pivotpos≤high。

    ②求解: 

         通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

    ③组合: 

         因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。

    void QuickSort(SeqList R,int low,int high)
       { //对R[low..high]快速排序
         int pivotpos; //划分后的基准记录的位置
         if(low<high){//仅当区间长度大于1时才须排序
            pivotpos=Partition(R,low,high); //对R[low..high]做划分
            QuickSort(R,low,pivotpos-1); //对左区间递归排序
            QuickSort(R,pivotpos+1,high); //对右区间递归排序
          }
        } //QuickSort
    

    实现

        /**
         * 调用者请确保传入正确的参数
         *
         * @param a     要排序的数组
         * @param left  0
         * @param right 数组的长度减去1
         */
        private static void quickSort(int[] a, int left, int right) {
            if (left < right) {
                int i = left;
                int j = right;
                int pivot = a[left];
                while (i < j) {
                    while (i < j && a[j] >= pivot) {
                        j--;
                    }
                    if (i < j) {
                        a[i] = a[j];
                        i++;
                    }
                    while (i < j && a[i] < pivot) {
                        i++;
                    }
                    if (i < j) {
                        a[j] = a[i];
                        j--;
                    }
                }
                a[i] = pivot;
    
    
                //递归排序
                quickSort(a, left, i - 1);
                quickSort(a, i + 1, right);
            }
        }
    

    展开全文
  • 快速排序JAVA实现

    2020-03-13 22:00:38
    快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。 该排序算法的基本思想是: 1.先从数列中取出一个数作为基准数。 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3....

    快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。

    该排序算法的基本思想是:

    1.先从数列中取出一个数作为基准数。

    2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

    3.再对左右区间重复第二步,直到各区间只有一个数。

    优点:极快,数据移动少;

    缺点:不稳定。
    算法实现
    假设我们现在要对{5,7,2,1,9,10,4,6,3,8}这个数组进行快速排序,我们应该怎么怎么做呢?

    1.立Flag
    Flag就是我们之前提到的基准数,为了将数据分区,立Flag是第一步也是最关键的一步。在这里我们将数组的第一个数设为基准数。

    2.探测
    对于{5,7,6,1,9,10,4,2,3,8}这个数组,第一次排序我们的Flag是5,我们分别从数组的左右两端开始“探测”。

    我们定义i指向数组的最左端,定义j指向数组的最右端。首先将j向左移,直到j指向的数小于5;再将i向右移,直到i指向的数大于5。最终i指向7,j指向3。
    在这里插入图片描述
    3.交换
    将3和7交换,数组变为{5,3,2,1,9,10,4,6,7,8}。第一次交换结束。

    在这里插入图片描述

    接下来继续探测、交换,探测、交换…

    4.Flag落位
    第二次交换结束后数组变为{5,3,2,1,4,10,9,6,7,8}。

    在这里插入图片描述在这里插入图片描述
    j指向9的位置,i指向4的位置,j继续向左移动,直到i的位置才找到小于5的值。

    此时i=j,我们只需将Flag落在这个位置:将5和4的值交换。数组变为{4,3,2,1,5,10,9,6,7,8}。

    在这里插入图片描述在这里插入图片描述

    至此,5这个Flag完成了它的历史使命,第一轮交换结束。
    在这里插入图片描述
    数组被划分为两个区,Flag左边是小于Flag的{4,3,2,1},Flag右边是大于Flag的{10,9,6,7,8}。
    在这里插入图片描述

    5.递归
    我们再分别对这两个区进行第二轮交换,交换结果是{1,3,2,4}和{8,9,6,7,10}

    对于{1,3,2}和{8,9,6,7}重复进行以上操作,直至得到不能拆解的单个数字,排序完成!

    下面用图展示整个排序过程:

    在这里插入图片描述
    JAVA代码

      public static void quickSort(int[] arr, int low, int high) {
            int i, j, temp, t;
            if (low > high) {
                return;
            }
            i = low;
            j = high;
            //temp就是基准位
            temp = arr[low];
    
            while (i < j) {
                //先看右边,依次往左递减
                while (temp <= arr[j] && i < j) {
                    j--;
                }
    
                //再看左边,依次往右递增
                while (temp >= arr[i] && i < j) {
                    i++;
                }
    
                //如果满足条件则交换
                if (i < j) {
                    t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
    
            }
    
            //最后将基准为与i和j相等位置的数字交换
            arr[low] = arr[i];
            arr[i] = temp;
    
            //递归调用左半数组
            quickSort(arr, low, j - 1);
            //递归调用右半数组
            quickSort(arr, j + 1, high);
        }
    
    展开全文
  • 快速排序 JAVA实现

    2019-03-29 21:46:00
    快速排序 每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。快速排序是不稳定的,时间复杂度(平均):nlogn public class QuickSort { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,647
精华内容 2,258
关键字:

快速排序java实现

java 订阅