Java写快速排序

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) 稳定
上一篇:两两交换链表中的节点


下一篇:go指针