欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java排序算法 快速排序

程序员文章站 2024-02-23 09:47:52
...

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。下面让我们一起来看快速排序。

AD:

快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序不稳定,O(log(n))的额外空间,时间复杂度为O(nlog(n)),不是自适应的。

快速排序(Quicksort)有几个值得一提的变种算法,这里进行一些简要介绍:

随机化快排:快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”

随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。

平衡快排(BalancedQuicksort):每次尽可能地选择一个能够代表中值的元素作为关键数据,然后遵循普通快排的原则进行比较、替换和递归。通常来说,选择这个数据的方法是取开头、结尾、中间3个数据,通过比较选出其中的中值。取这3个值的好处是在实际问题(例如信息学竞赛……)中,出现近似顺序数据或逆序数据的概率较大,此时中间数据必然成为中值,而也是事实上的近似中值。万一遇到正好中间大两边小(或反之)的数据,取的值都接近最值,那么由于至少能将两部分分开,实际效率也会有2倍左右的增加,而且利于将数据略微打乱,破坏退化的结构。

外部快排(ExternalQuicksort):与普通快排不同的是,关键数据是一段buffer,首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序,然后从被排序数组的开头(或者结尾)读入下一个元素,假如这个元素小于buffer中最小的元素,把它写到最开头的空位上;假如这个元素大于buffer中最大的元素,则写到最后的空位上;否则把buffer中最大或者最小的元素写入数组,并把这个元素放在buffer里。保持最大值低于这些关键数据,最小值高于这些关键数据,从而避免对已经有序的中间的数据进行重排。完成后,数组的中间空位必然空出,把这个buffer写入数组中间空位。然后递归地对外部更小的部分,循环地对其他部分进行排序。

三路基数快排(Three-way Radix Quicksort,也称作MultikeyQuicksort、Multi-key Quicksort):结合了基数排序(radixsort,如一般的字符串比较排序就是基数排序)和快排的特点,是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点,即multikey,如一个字符串,每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据,首先仅考虑这个元素的第一个key(字母),然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对“小于”和“大于”部分进行排序,基于下一个key对“等于”部分进行排序。

快速排序是目前使用的最广泛的排序算法了,快速排序的核心在于分割算法,也可以说是最有技巧的部分。希望通过本文的介绍,能给你带来帮助。

代码一:

 

 public static voidquickSort(int[] a, int low, int high) {

     int n =a.length;

     int i =low;

     int j =high;

     int temp= a[low];

     while (i< j) {

     

      //必须从右边开始扫描,否则从左边开始扫描遇到一个比它大的元素时(左边不是有一个空位吗?但是放到左边肯定是不合适)应该放到右边,放到哪里呢,放到任何地方都会覆盖掉一个数据 这样没有利用上这个缺口 严重错误

      while(i < j && a[j]>= temp) {

      j -- ;//放过

      }

     if(i<j) {

      a[i] = a[j] ;

      i ++ ; //放过,并开始左端循环

      }

      while(i< j && a[i]< temp) { //注意 :" < " 而不是<=这个细节说明即使和temp相等也要放到它的后面这样保证了-在数值相同时,保持原有顺序的原则!

      i ++ ;

      }

      if(i< j) {

      a[j] = a[i] ;

      j -- ;

      }

     }

     a[i] =temp ;

    //有可能i=low 如 :a[low]是最小的,一开始循环就一直j-- 一直减到了i ==j然后赋值(即它本来就应该在第一位),也有可能a[low]是最大的,一直i++到high。如果是这样就不用对那个子区间排序了,所以下面用if语句

     if(i> low) quickSort(a, low, i-1) ;

     if(i< high) quickSort(a , i+1, high) ;

     

    }

    public static voidmain(String[] args) {

     

     int [] a= {49,38,65,97,76,13,27};

    quickSort(a, 0 , a.length-1) ;

     print(a);

    }

    //为了打印数组的方便增加一个方法print()

    public static voidprint(int [] a) {

     int n =a.length ;

     for(inti=0;i<n;i++) {

     System.out.print(a[i] + "  ") ;

     if((i+1) % 5 == 0) {

      System.out.println() ;

      }

     }

    System.out.println( ) ;

    } 

    }



代码二:


public class quickSort2 {
 
public static void main(String[] args){ 
  //声明数组 
   int[] nums ={49,38,65,97,76,13,27,-77}; 
  //应用快速排序方法 
   quickSort(nums, 0,nums.length-1); 
  //显示排序后的数组 
   for(int i = 0; i< nums.length; ++i) { 
    System.out.print(nums[i] +","); 
   } 
  System.out.println(""); 
} 
 
public static void quickSort(int[] a, int M, int K){ 
   int lo =M; 
  System.out.println("lo是从左到右,初始值为:"+lo);
   int hi =K; 
  System.out.println("hi是从右到左,初始值为:"+hi);
   if (lo >=hi) {
     System.out.print("lo:"+lo+"   hi:"+hi);
  System.out.println("  因为lo:"+lo+">=hi:"+hi+"被返回!!");
    return; 
   }
  //确定指针方向的逻辑变量 
   booleantransfer=true; 
   while (lo != hi){ 
   System.out.println("lo的值是:"+lo);
   System.out.println("hi的值是:"+hi);
   
   
     if(a[lo] > a[hi]) { 
    //交换数字 
      int temp = a[lo]; 
      a[lo] = a[hi]; 
      a[hi] = temp; 
      System.out.println("交换数字了!"+a[lo]+"和"+a[hi]+"进行了交换,temp的值为:"+temp);
      
    //显示每一次比较的数组数字的变化 
      System.out.print("现在数组的排列顺序为:");
    for(int i = 0; i< a.length; ++i) { 
      System.out.print(a[i] +","); 
    } 
   System.out.println("特殊记号M:"+M);
      //决定移动,還是不動,这个开关是个钟摆,轮流真假两种状态!触发条件是发生交换!
      transfer = (transfer == true) ? false :true; 
      System.out.println("开关动了,指针要移动了!开关transfer的值为:"+transfer);
    } 
     
     
    //将指针向前或者向后移动,默认情况下lo++,注意!有交换不一定会让transfer变为true!--,
    if(transfer) {
      hi--; 
      System.out.println("hi被减了1");
    }
     else{
      lo++; 
      System.out.println("lo被加了1");
     }    
   }
  System.out.println("while循环退出,lo和hi相等:"+lo+"="+hi);
  //将数组分开两半,确定每个数字的正确位置,return的时候会单独做这个操作 
  
  lo--; 
  hi++; 
  System.out.println("将数组分开两半,确定每个数字的正确位置,现在lo和hi的值为:"+lo+"  "+hi);
  System.out.println("M的值为:"+M);
  //神奇的M,因为没有传任可值过去,所以M一直为最原先程序所传过来的“0”
  System.out.println("quickSort(a, M, lo)");
  System.out.println("调用程序之前 M:"+M+"  K:"+K+"   hi:"+hi+"   lo:"+lo );
   quickSort(a, M, lo);  
  System.out.println("调用程序之后 M:"+M+"  K:"+K+"   hi:"+hi+"   lo:"+lo );
   
   
  System.out.println("quickSort(a, hi, K);");
   quickSort(a, hi,K);
  System.out.println("调用程序之后 M:"+M+"  K:"+K+"   hi:"+hi+"   lo:"+lo );
} 
}


转载于:https://www.cnblogs.com/xiaowangba/archive/2012/08/02/6314534.html