首页 > 代码库 > 快速排序

快速排序

2024-07-11 08:11:49   228人阅读

快速排序的基本思想：

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交 换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。

 1 package test; 2  3 import java.util.Random; 4  5 /** 6  * 快速排序平均时间复杂度为O(nlogn)，最坏为O(n的平方) 7  * @author xixingwang 8  * 9  */10 public class QuickSort {11     12   public static void main(String[] args) {13       int iLength = 5;14       int[] iArgs = new int[iLength];15       for(int i = 0; i < iLength; i++){16           Random objRandom = new Random();17           iArgs[i] = objRandom.nextInt(1000);18       }19       quickSort(iArgs,0,iArgs.length-1);20       21       for(int i = 0; i < iArgs.length; i++) {22         System.out.print(iArgs[i] + " ");23       }24   }25   26   /**27    * 递归循环数据28    */29   private static void quickSort(int[] args,int left,int right) {30      if( left < right) {31          //数据从left到right坐标的数据进行排序32          int iIndex = partition(args,left,right); //iIndex 是基数放在数据位置33 34           //递归算法，对于基数左边排序35          partition(args,left,iIndex-1); //为什么left不能从036           //递归算法，对于基数右边排序37          partition(args,iIndex+1,right);//为什么 right不等于length38      }39   }40   41   /**42    * 确定基数左边的数都比它小，右边的数都比它大 43    */44   private static int partition(int[] args,int left,int right) {45       int iBase = args[left]; //基准数46       while (left < right) {47          //从右向左找出第一个比基准数小的数48           while( left < right && args[right] >= iBase) {49               right--;50           }51           args[left] = args[right];//比中轴小的记录移到低端 52           53           //从左向右找出第一个比基准数大的数54           while( left < right && args[left] <= iBase) {55               left++;56           }57           args[right] = args[left];//比中轴大的记录移到高端58       }59       args[left]= iBase;//中轴记录到尾60       return left;61   }62 }

 

 1 public static void quickSort(int data[], int start,int end){ 2        3       if(start < end){ 4           int base = data[start]; 5           int left = start; 6           int right = end; 7           while(left < right){ 8                9               while(left<right&&data[left]<=base){10                   left++;11               }12               data[right] = data[left];13               while(left<right&&data[right]>=base){14                   15                   right--;16                   17               }18               data[left] = data[right];19           }20           21           data[left] = base;22           23           quickSort(data,start,left-1);24           quickSort(data, left+1, end);25           26       }27   }

 


联系
我们