快速排序

算法思想：

每趟取一个参照记录，称为枢轴（或支点），先从右向左，逐个记录与枢轴比较，如果逆序则交换，再从左向右，逐个记录与枢轴比较，如果逆序则交换，反复进行，直到左右相遇，结束一趟排序，并将枢轴记录交换到最终所在的位置上。所有大于枢轴的记录记录在右边，小于的在左边，一趟快速排序过程称为一个划分。然后分别对左右两部分进行相同的划分（或分割），得到4部分，再对每部分做相同划分，依次继续下去，直到每个小部分只有一个记录，排序结束。显然，对部分的划分操作完全相同，只是范围需修改，因此可以用递归实现，且最多经过[log 2 （n +1）趟划分，排序结束。

算法实现：分解为两个函数，一趟划分函数，递归调用函数。
以下是快速排序的非递归算法实现

  int  partition ( RecTypr  R[ ] ,  int  low , int  high  )

         {  i= low ; j = high ; R[0] = R ; x = R.key ;

            while ( i < j )

               {  while ( i < j && R[j].key >= x ) j - - ;

                  if ( i < j ) R = R[j] ;  //

                  while ( i < j && R[j].key <= x )  i ++ ;

                  if ( i < j ) R[j] = R ;

                }

            R = R[0] ;

            return  i ;

         }

   Void  quicksort (RecTypr  R[ ] ,  int  n )

           {  typedef  struct

                 {  int  low , high  

} Node ;

             Node s[n+1] ;

             int  top = 1 ;

s[top].low = 1 ;  s[top].high = n ;

             while ( top > 0 )

                 {  ss = s[top].low ;  tt = s[top].high ;  top - - ;

                    if ( ss < tt )

                       {  k = partition ( R ,  ss ,  tt ) ;

                          if ( k – ss > 1 )

                            {  s[++top].low = ss ;

                              s[top].high = k – 1 ;

                            }

                          if ( k – tt > 1 )

                            { s[++top].low = k+1 ;

                              S[top].high = tt ;

                            }

                        }

                  }

            }

1. package com.itheima.util;
   
2. 
   
3. /**
   
4. * 排序工具类
   
5. *
   
6. * @author mrng
   
7. *
   
8. */
   
9. public class SortUtils {
   
10.         /**
    
11.          * 快速排序 如果调用此方法，次方法会再掉用quickSort(String[] strArr, int left, int rigth)方法
    
12.          * left默认为0， right默认为strArr.length-1
    
13.          *
    
14.          * @param strArr
    
15.          */
    
16.         public static void quickSort(int[] arr) {
    
17.                 quickSort(arr, 0, arr.length - 1);
    
18.         }
    
19. 
    
20.         /**
    
21.          * 快速排序 此方法可以对数组需要排序的区间进行定制
    
22.          *
    
23.          * @param strArr
    
24.          * @param left
    
25.          * @param right
    
26.          */
    
27.         public static void quickSort(int[] arr, int left, int right) {
    
28.                 // 数组中间的元素
    
29.                 int middle = arr[(left + right) / 2];
    
30.                 // 临时变量，用于交换数组元素使用
    
31.                 int temp;
    
32.                 // 向后搜索的指针
    
33.                 int i = left;
    
34.                 // 向前搜索的指针
    
35.                 int j = right;
    
36. 
    
37.                 do {
    
38.                         while (arr[i] < middle && i < right)
    
39.                                 i++; // 找出左边比中间值大的数
    
40.                         while (arr[j] > middle && j > left)
    
41.                                 j--; // 找出右边比中间值小的数
    
42.                         if (i <= j) { // 将左边大的数和右边小的数进行交换
    
43.                                 temp = arr[i];
    
44.                                 arr[i] = arr[j];
    
45.                                 arr[j] = temp;
    
46. 
    
47.                                 i++;
    
48.                                 j--;
    
49.                         }
    
50.                 } while (i <= j); // 当两个指针交错时停止
    
51. 
    
52.                 // 将数组分开两半，确定每个数字的正确位置
    
53.                 if (i < right) {
    
54.                         quickSort(arr, i, right);
    
55.                 }
    
56.                 if (j > left) {
    
57.                         quickSort(arr, left, j);
    
58.                 }
    
59.         }
    
60. 
    
61.         /**
    
62.          * 冒泡排序法
    
63.          *
    
64.          * @param arr
    
65.          */
    
66.         public static void BubbleSort(int[] arr) {
    
67.                 for (int i = 0; i < arr.length - 1; i++) {
    
68.                         for (int j = 0; j < arr.length - i - 1; j++) {
    
69.                                 if (arr[j] > arr[j + 1]) {
    
70.                                         arr[j] = arr[j] ^ arr[j + 1];
    
71.                                         arr[j + 1] = arr[j] ^ arr[j + 1];
    
72.                                         arr[j] = arr[j] ^ arr[j + 1];
    
73.                                 }
    
74.                         }
    
75.                 }
    
76.         }
    
77. 
    
78.         /**
    
79.          * 选择排序法
    
80.          */
    
81.         public void SelectSort(int[] arr) {
    
82.                 for (int i = 0; i < arr.length - 1; i++) {
    
83.                         for (int j = i + 1; j < arr.length; j++) {
    
84.                                 if (arr[i] > arr[j]) {
    
85.                                         arr[i] = arr[i] ^ arr[j];
    
86.                                         arr[j] = arr[i] ^ arr[j];
    
87.                                         arr[i] = arr[i] ^ arr[j];
    
88.                                 }
    
89.                         }
    
90.                 }
    
91.         }
    
92. }

复制代码

快速排序是对冒泡排序的一个升级
一趟快速排序的规则
就是设定一个枢轴，把段表分割成两段
一段中的数据都比枢轴小，另一边都比枢轴的数据大
这就是快速排序的一趟排序
然后分别对这分割完的数据段再进行快速排序
如此下去就会排出有序序列
可以利用递归的思想



首先要先定义一个方法实现一趟快速排序，并且该方法返回枢轴位置
例如：
//定义一个一趟快速排序的私有方法供内部使用
        private int yiTangSort(int[] s,int low,int high)
        {
                //定义一个变量作为枢轴的临时容器
                int pivotkey=0;
               
                pivotkey=s[low];//枢轴记录关键字
               
                //如果数据长度不小于1,就开始从数据的两端交替的向中间扫描
                while(low<high)
                {
                        while(low<high&&s[high]>=pivotkey)//将比枢轴小的数据移到低端
                                high--;
                        s[low]=s[high];
                        while(low<high&&s[low]<=pivotkey)//将比枢轴大的数据移到高端
                                low++;
                        s[high]=s[low];
                }
                s[low]=pivotkey;//将枢轴添加到指定位置
                return low;//返回枢轴位置
        }



然后再定义一个方法判断枢轴并递归调用一趟排序的方法
例如
//定义一个私有快速排序的方法供内部使用
        private void quickSort(int[] s,int low,int high)
        {
                int pivot=0;//定义一个变量用来接受枢轴的位置
               
                if(low<high)//如果该数据段长度大于1开始排序和递归
                {
                        pivot=yiTangSort(s,low,high);
                        quickSort(s,low,pivot-1);
                        quickSort(s,pivot+1,high);
                }
                        
        }


然后对外部暴露出去一个快速排序的方法
例如：
//定义一个快速排序的方法供外部使用
        public void kuaiSuPaiXu(int[] s)
        {
                int low=0;
                int high=s.length-1;
                quickSort(s,low,high);
        }
以上只是三个方法
楼主可以试着把他们封装在一个类中，以实现完整的快速排序