Java写快速排序
时间复杂度:O(nlog2n)
public static void quickSort(int nums[],int left,int right){
int l=left;
int r=right;
int key=nums[left];
while(l<r){
while(nums[r]>=key && l<r){
r--;
}
while(nums[l]<=key && l<r){
l++;
}
int temp=nums[l];
nums[l]=nums[r];
nums[r]=temp;
}
//当前i值是比标志值key小,应该放在key值左边,即对调key与nums[i]位置
//交换标志值与快排完后的i
//key=nums[left];在函数第三行
nums[left]=nums[l];
nums[l]=key;
//递归完成对key值左右的子数组的快排
quickSort(nums,left,l-1);
quickSort(nums,l+1,right);
}
几种排序算法比较:
排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
希尔排序 | O(n1.3) | O(n2) | O(n) | O(1) | 不稳定 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
桶排序 | O(n+k) | O(n2) | O(n) | O(n+k) | 稳定 |
基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |