常见排序算法——快速排序
快速排序核心就是分治法,通过划分将待排序的序列分成前后两部分,其中前一部分的数据都比后一部分的数据要小,然后再递归调用函数对两部分的序列分别进行快速排序,以此使整个序列达到有序,其时间复杂度为O(nlogn)。该算法步骤如下:
1、从序列中任选一个数作为基准数,一般就使用第一个数;
2、分区,将大于基准得数房右边,小于基准得数放左边,注意一定要先右后左;
3、对左右区间分别执行1、2步骤,直到每个区间只有一个数为止。
public void sort(int leftLimit, int rightLimit, int[] nums){ int i = leftLimit; int j = rightLimit; int mid = nums[i]; while(i<j){ while(i<j&&nums[j]>mid){ j--; } if(i<j){ nums[i++]=nums[j]; } while(i<j&&nums[i]<mid){ i++; } if(i<j){ nums[j--]=nums[i]; } } nums[i]=mid; if(leftLimit<i-1){ sort(leftLimit, i-1, nums); } if(i+1<rightLimit){ sort(i+1, rightLimit, nums); } }
分类: 数据结构与算法