快速排序-交换排序

快速排序属于交换排序的一种，若有两个相同的元素，则它们的位置会发生变化，是一种不稳定的排序算法 是所有内部排序算法中平均性能最优的

空间效率：快速排序时递归的，需要一个辅助工具 栈，  空间效率与栈的深度有关，进行n-1次递归调用，O(n)    平均情况 O(log_2n)

时间效率： 运行时间与划分对称有关，最坏情况O(n^2)

主要思想：挖坑跳数+分治

1 在待排序的序列中，选择一个基准数一般是序列的首尾数或中间数

2 从右到左，遍历序列，查找比基准数小的元素，放在左边

3 从左往右，遍历序列，查找比基准数大的元素，放在右边

待排序序列    4 1 3 7 6 2 8   

选取序列第一个数作为基准值4     i   指向序列的头部    j  指向序列的尾部 下标初始值为0 结束值6

坑 1 3 7 6 2 8 

从右往左，查找比基准数小的元素，8比4大不符合，2比4小 与坑互换位置。下标 j--=5

2 1 3 7 6 坑 8 

转换，从左往右，查找比基准数大的元素，2比4小，1比4小，3比4小都不符， 7比4大符合，与坑互换位置    下标 i++= 3

2 1 3 坑 6 7 8 

转换，从右往左，查找比基准值小的元素，7比4大， 6 比4大不符，此时i++等于 j--等于3 下标位置一致 将元素填入坑中

第一轮排序完成        2 1 3 4 6 7 8 

根据基准值 序列分为左右两个子序  左子序:2 1 3     右子序 4 6 7 8   对左右序列递归执行前3步。

左子序排序： 获取基准值2

坑 1 3 

从右往左，查找比基准值小的元素，3比2大，1比2小符合 j--=1 交换坑与1的位置

1 坑 3

从左往右，查找比基准值大的元素，1 小于2不符 i++=1  下标位置重合，将基准值2填入坑中

1 2 3 

左子序排序完成 1 2 3       此时右子序目测不用排序。

快速排序完成    1 2 3  4 6 7 8 

伪代码：

i=start
 
j=end
 
//获取基准值
 
temp=arr[start]
 
while(i
    //从右往左，查找比基准值小的元素，放在序列左边
 
    while(i=temp){
 
        j--;
    }
    //如果查找的元素比基准值小，该元素与坑互换位置
    if(i
        arr[i]=arr[j];
        i++;
 
    }
    //从左往右，查找比基准值大的元素，放在序列的右边
    while(i
        i++;
    }
    //如果从左往右查找的元素比基准值大，该元素放在序列的右边，该元素与坑 互换位置
    if(i
        arr[j]=arr[i]
    }
 
}
//把基准数放到i=j位置上
arr[i]=temp
//递归左部分，子序进行快排
QuickSort(arr,start,i-1)
//递归右部分，子序进行快速排序
QuickSort(arr,i+1,end);
return arr;