排序算法5--交换排序--快速排序

快速排序

1.快速排序是有冒泡排序改进的来的。在冒泡排序的过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果通过两个不相邻记录进行交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中一次交换可以消除多个逆序

算法方法：

　　从右侧找第一个比key值小的进行交换，从左侧找第一个比key值大的进行交换，但是交换的并非是key值
　　最后得到key值左边都是比key小的，右边是比key大的，但是左右区间并不一定是有序的，需要进行递归调用
　　元素正序和逆序时效果最差，数据越无序，效果越好

例如：

　　  初始：   3 5 6 2 4 1(3作为key值，从后向前找第一个比3小的值为1，与3交换；从前向后找第一个比3大的值5与3交换，前面的逐渐加1，后面的逐渐减1，直到到同一个位置)
　　第一步：1 2 3 6 4 5 (3左边都是比3小的，3后面都是比3大的，但是区间内部不一定是有序的，需要进行递归再次调整)
　　第二步：1 2 3 6 4 5 
　　第三步：1 2 3 6 4 5 
　　第四步：1 2 3 5 4 6 
　　第五步：1 2 3 4 5 6

　　第六步：1 2 3 4 5 6

数据结构课本上有一个例子：

2.时间复杂度

最好情况下(每一趟排序后都能将记录序列均匀的分割成两个长度大致相等的子表，类似折半查找)时间复杂度是O(logn)

最坏情况(在待排序序列已经排好序的情况下，其递归成单只树，每次划分只能得到一个比上一次少一个记录的子序列)时间复杂度是O(n)

平均时间复杂度是O(nlogn)

具体时间复杂度等分析，请参考：http://www.cnblogs.com/zhangxue521/p/6748085.html

3.算法特点

   ①.记录非顺次的移动导致排序方法是不稳定的

   ②.排序过程中需要定位表的上界和下界，所以适合顺序存储，不适合链式

   ③.元素正序和逆序时效果最差，数据越无序，效果越好

java实现：

package 平时常用;

import java.util.Scanner;

public class _3快速排序 {
  public static void main(String[] args) {
      int a[] = new int[6];
      Scanner scanner = new Scanner(System.in);
      for (int i = 0; i < a.length; i++) {
          a[i] = scanner.nextInt();
      }
      sort(a, 0, a.length - 1);
      for (int m : a) {
          System.out.print(m+" ");
      }
         
  }
  public static void sort(int a[],int low,int high){
      int key = a[low];//基数
      int start = low;
      int end = high;
      //从前往后找比基数大的放基数右边，从后往前找比基数小的放基数左边
      while(end >start){//从两端交替向中间交换
          //从后往前找,找比关键值小的，如果没有小的，end--
          while(end >start && a[end] >= key) end--;
          if (a[end] <= key) {//找到比key值小的了，交换位置
              int temp = a[end];
              a[end] = a[start];
              a[start] = temp;
          }
        //从前往后找,找比关键值大的，如果没有大的，strat++
          while(end >start && a[start] <= key) start++;
          if (a[start] >= key) {//找到比key值小的了，交换位置
              int temp = a[start];
              a[start] = a[end];
              a[end] = temp;
          }
        //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
      }
      //测试每轮的输出
//      for (int m : a) {
//            System.out.print(m+" ");
//        }
//        System.out.println();
//        递归
      key = a[start];
      if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
      if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1到最后一个      
  }
}

js实现：

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var key= Math.floor(arr.length / 2); //取基准点  
　　var pivot = arr.splice(key , 1);  //取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]  
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
 //递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1；  
　　return quickSort(left).concat([pivot], quickSort(right));
};
a = [2,5,4,7,1,4,6,6]
console.log(quickSort(a))

python实现：

def quickSort(a):
    if len(a) <= 1:
        return a
    else:
        left =[]
        right = []
        key = a.pop()
        for x in a:
            if x < key:
                left.append(x)
            else:
                right.append(x)
        return quickSort(left)+[key]+quickSort(right)