排序数组
1、使用快速排序
代码：
/**
* 数组内元素交换
* @param nums 输入数组
* @param i 元素1下标
* @param j 元素2下标
*/
private void swap(int[] nums, int i, int j) {
int temp = nums [i];
nums [i] = nums [j];
nums [j] = temp;
}
/**
* 快速排序
*
* @param nums 输入数组
* @param left 划分左边界
* @param right 划分右边界
*/
private void quickSort(int[] nums, int left, int right) {
// 递归返回条件，和分区排序结束
if (right-left <=0) {
return;
}
// 选择数组右边界值作为分区节点
int pivot = nums[right];
// 从数组左边界值开始维护分区
int partition=left-1;
// 遍历当前分区内元素
for (int i = left; i <= right-1; i++) {
if ((nums [i] < pivot) ) {
// 将小于pivot的值交换到partition左边
// 将大于等于pivot的值交换到partition右边
partition++;
swap(nums, partition, i);
}
}
// 将分区节点插入到数组左右分区中间
partition++;
swap(nums, partition, right);
// 分区节点排序完成
// 左分区继续排序，右分区继续排序
quickSort(nums,left, partition-1);
quickSort(nums,partition+1, right);
}
/**
* 排序数组入口函数
*
* @param nums 输入数组
* @return 返回完成排序的数组
*/
public int[] sortArray(int[] nums) {
if (nums == null || nums.length ==0) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}2、快速排序的思想
总体上，快速排序是遵循分治思想的，也就是大问题划分为小问题。
1）大问题划分为小问题
快速排序与插入、冒泡等的区别，就是对输入的序列做划分。以数组A[p..r]为例，选择一个元素pivot作为分区节点完成划分后，左边分区是小于pivot的元素，右边是大于等于pivot的元素，中间是分区节点pivot。
2）解决小问题
每次划分结束，对左右分区继续递归快排，中间分区不再处理。
这里可以看到，每次划分实际上就是排序。其中，中间分区（节点pivot）排序完成，左右分区继续快排。
3）合并得到大问题的解
在当前的数组例子中，所有的分区快排都在原址上进行，不需要额外合并处理。
3、快速排序的设计逻辑
本质上，每次划分实际上就是排序。
1）大问题分解为小问题，并递归解决小问题
QUICKSORT(A,p,r)
if (p<r)
q=PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)2）数组的划分
算法的关键部分是PARTITION过程，实现了对子数组A[p..r]的原址重排。
PARTITION(A,p,r)
x=A[r]
i=p-1
for j=p to r-1
if (A[j]<=x)
i++
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1;3）循环不变量
在快速排序划分的每一轮迭代里，将当前数组区间分为三个区域，每一个区域都满足一定的性质。我们将这些性质称为循环不变量：
在for循环体中，对于任意数组下标k, 有
- 若p<=k<=i, 则A[k]<=x;
- 若i+1<=k<=j-1, 则A[k]>x;
- 若k=r, 则A[k]=x
评论 (0)
