常见的排序
- 时间复杂度O(n^2): 插入, 冒泡, 交换
- 时间复杂度O(n lgn): 快速, 希尔, 堆栈, 并归
关于快速排序
void quickSort(int[] arr,int low,int hight){
int pivot = getPivot(arr,low,hight);
int pivotVal = arr[pivot];
int i=low;
int j=hight;
while(i<j)
{
while(i<j&&int[i]<pivotVal ){
i++;
}
while(i<j&&int[j]>pivotVal ){
j--;
}
if(i>=j){
break;
}else{
swap(arr,i,j);
}
}
swap(arr,i,pivot );
quickSort(arr,i,pivot -1);
quickSort(arr,pivot +1,j);
}
空间复杂度 lg(n); 最差的空间复杂度(n)
解决空间复杂度的getPivot() 方法的实现.
比如随机选三个数, 去中间的数作为 pivot
