快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
function quickSort(arr,left,right){
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;
if(left < right){
partitionIndex = partition(arr,left,right);
quickSort(arr,left,partitionIndex-1);
quickSort(arr,partitionIndex+1,right);
}
return arr;
}
function partition(arr,left,right){ //分区操作
var prvot = left, //设定基准值（pivot）
index = pivot + 1;
for(var i = index;i <= right;i++){
if(arr[i] < arr[pivot]){
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index - 1);
return index-1;
}
function swap(arr,i ,j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition2(arr,low,high){
let pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
--high;
}
arr[low] = arr[high];
while(low < high && arr[low] <= pivot){
++low
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
function qunickSort2(arr,low,high){
if(low < high){
let pivot = pratition2(arr,low,high);
quickSort2(arr,low,pivot - 1);
quickSort2(arr,pivot + 1,high);
}
return arr;
} def quickSort(arr,left=None,right=None):
left = 0 if not isinstance(left,(int,float)) else left
right = len(arr)-1 if not isinstance(right,(int,float)) else right
if left < right:
partitionIndex = partition(arr,left,right)
quickSort(arr,left,partitionIndex-1)
qunckSort(arr,partitionIndex+1,right)
return arr
def partition(arr,left,right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr,i,index0
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr,i,j):
arr[i],arr[j] = arr[j],arr[i]
func quickSort(arr []int) []int{
return _quickSort(arr,0,len(arr)-1)
}
func _quickSort(arr []int,left,right int) []int{
if left < right {
partitionIndex := partition(arr,left,right)
_quickSort(arr,left,partitionIndex-1)
_quickSort(arr,partitionIndex+1,right)
}
return arr
}
func partition(arr []int,left,right int)int{
pivot := left
index := pivot + 1
for i := index; i <= right; i++{
if arr[i] < arr[pivot]{
swap(arr,i,index)
index += 1
}
}
swap(arr,pivot,index-1)
return index - 1
}
func swap(arr []int, i, j int){
arr[i],arr[j] = arr[j],arr[i]
} Partition1(int A[],int low,int high){
int pivot = A[low];
while(low < high){
while(low<high && A[high] >= pivot){
--high;
}
A[low] = A[high];
while(low < high && A[low] <= pivot){
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[], int low, int high)
{
if(low < high){
int pivot = Partition1(A,low,high);
QuickSort(A,low,pivot - 1);
QuickSort(A,pivot + 1,high);
}
} public class QuickSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//对arr进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
return quickSort(arr,0,arr.length - 1);
}
private int[] quickSort(int[] arr, int left, int right){
if(left < right){
int partitionIndex = partition(arr,left,right);
quicksort(arr,left,partitionIndex - 1);
quickSort(arr,partitionIndex + 1,right);
}
return arr;
}
private int partition(int[] arr, int left, int right){
//设定基准值(pivot)
int pivot = left;
int index = pivot + 1;
for(int i = index; i<= right; i++){
if(arr[i] < arr[pivot]){
swao(arr,i,index);
index++;
}
}
swap(arr,pivot,index - 1);
return index - 1;
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
堆排序的平均时间复杂度为 Ο(nlogn)。
1.将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
2.把堆首（最大值）和堆尾互换；
3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4.重复步骤 2，直到堆的尺寸为 1。
var len; //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr){ //建立大顶堆
len = arr.length;
for(var i = Math.floor(len/2);i>=0;i--){
heapify(arr,i);
}
}
function heapify(arr,i){ //堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if(left < len && arr[left] > arr[largest]){
largest = left;
}
if(right < len && arr[right] > arr[largest]){
largest = right;
}
if(largest != i){
swap(arr,i,largest);
heapify(arr,largest);
}
}
function swap(arr,i,j){
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr){
buildMaxHeap(arr);
for(var i = arr.length-1; i > 0; i--){
swap(arr,0,i);
len--;
heapify(arr,0);
}
return arr;
} def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr,i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr,i,largest)
heapify(arr,largest)
def swap(arr,i,j):
arr[i],arr[j] = arr[j],arr[i]
def heapSort(arr):
global arrLen
aeeLen = len(arr)
buildMasxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -= 1
heapify(arr,0)
return arr func heapSort(arr []int) []int {
arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
swap(arr, 0, i)
arrLen -= 1
heapify(arr, 0, arrLen)
}
return arr
}
func buildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {
heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
if largest != i {
swap(arr, i, largest)
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}public class HeapSort implements IArraySort{
@Override
public int[] sort(int[] sourceArray) throws Exception{
//对arr进行拷贝，不改变参数内容
int[] arr = Array.copyOf(sourceArray,sourceArray.length);
int len = arr.length;
buildMaxHeap(arr,len);
for(int i = len - 1; i > 0; i--){
swap(arr,0,i);
len--;
heapify(arr,0,len);
}
return arr;
}
private void buildMaxHeap(int[] arr,int i , int len){
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if(left < len && arr[left] > arr[largest]){
largest = left;
}
if(right < len && arr[right] > arr[largest]){
largest = right;
}
if(largest != i){
swap(arr,i,largest);
heapify(arr,length,len);
}
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} 
