排序算法四：快速排序(Quicksort)

快速排序(Quicksort)，因其排序之快而得名，虽然Ta的平均时间复杂度也是O(nlgn)，但是从后续仿真结果看，TA要比归并排序和堆排序都要快。

快速排序也用到了分治思想。

（一）算法实现

 protected void quicksort(int[] array, int first, int last) {

         int pivot = array[first];

         int i = first;

         int j = last - 1;

         boolean serachBig = true;

         while (i < j) {

             if (serachBig) {

                 if (array[j] < pivot) {

                     array[i] = array[j];

                     i++;

                     serachBig = false;

                 } else {

                     j--;

                 }

             } else {

                 if (array[i] > pivot) {

                     array[j] = array[i];

                     j--;

                     serachBig = true;

                 } else {

                     i++;

                 }

             }

         }

         array[i] = pivot;

         if (i - first > 1) {

             quicksort(array, first, i);

         }

         if (last - i > 2) {

             quicksort(array, i + 1, last);

         }

     }

Quicksort

1）快速排序的平均时间复杂度也是O(nlgn)

2）考虑递归，快速排序空间复杂度是O(logn)，不是原地排序

3）快速排序属于比较排序

4）快速排序不是稳定排序算法

（二）仿真结果

**************************************************
Number to Sort is:2500
Array to sort is:{378132,303655,213274,506865,348563,122685,857064,624884,376943,281167...}
Cost time of 【QuickSort】 is(milliseconds):0
Sort result of 【QuickSort】:{93,862,991,1285,2737,2938,3119,3372,3933,4647...}
**************************************************
Number to Sort is:25000
Array to sort is:{737677,533972,6498,772664,516805,635063,278963,284929,577222,593745...}
Cost time of 【QuickSort】 is(milliseconds):2
Sort result of 【QuickSort】:{1,247,270,375,386,428,431,515,588,623...}
**************************************************
Number to Sort is:250000
Array to sort is:{481818,650680,957183,733420,611440,739781,495686,560166,942993,492550...}
Cost time of 【QuickSort】 is(milliseconds):23
Sort result of 【QuickSort】:{0,6,10,17,20,22,23,26,32,37...}

相关代码：

 package com.cnblogs.riyueshiwang.sort;

 import java.util.Arrays;

 public class QuickSort extends abstractSort {

     @Override

     protected void sort(int[] toSort) {

         quicksort(toSort, 0, toSort.length);

     }

     protected void quicksort(int[] array, int first, int last) {

         int pivot = array[first];

         int i = first;

         int j = last - 1;

         boolean serachBig = true;

         while (i < j) {

             if (serachBig) {

                 if (array[j] < pivot) {

                     array[i] = array[j];

                     i++;

                     serachBig = false;

                 } else {

                     j--;

                 }

             } else {

                 if (array[i] > pivot) {

                     array[j] = array[i];

                     j--;

                     serachBig = true;

                 } else {

                     i++;

                 }

             }

         }

         array[i] = pivot;

         if (i - first > 1) {

             quicksort(array, first, i);

         }

         if (last - i > 2) {

             quicksort(array, i + 1, last);

         }

     }

     public static void main(String[] args) {

         for (int j = 0, n = 2500; j < 3; j++, n = n * 10) {

             System.out

                     .println("**************************************************");

             System.out.println("Number to Sort is:" + n);

             int[] array = CommonUtils.getRandomIntArray(n, 1000000);

             System.out.print("Array to sort is:");

             CommonUtils.printIntArray(array);

             int[] array1 = Arrays.copyOf(array, n);

             new QuickSort().sortAndprint(array1);

         }

     }

 }

QuickSort.java

巴特西

排序算法四：快速排序(Quicksort)

最新文章

热门文章