算法简介
快速排序（Quick Sort） 是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换直接消除多个逆序，则会大大加快排序的虚度。快速排序方法中的一次交换可以消除多个逆序。
算法步骤
在待排序的n个记录中任取一个记录（通常选取第一个记录）作为枢轴，设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换的前面，把所有大于pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢轴放置在分界处的位置。然后对左右两个子表重复上述过程，直到每一个子表只有一个记录时，排序完成。换句话说，就是每一趟排序都将一条记录放在了正确的位置上。（正确位置就是完成排序时它所处的位置）
具体步骤
选择待排序表中第一个记录作为枢轴，保存在变量pivotkey中。附设两个指针low和high,初始时分别指向表的上界和下界（第一趟时，low = 0;high = nums.length）。从表的最右侧位置依次向左侧搜索，当找到第一个值小于pivotkey的记录时，将其移动到low处。具体操作是：当low < high时，若high所指记录大于等于pivotkey，则向左移动指针high；否则移动该记录。然后从表的最左侧位置依次向右侧搜索，找到第一个关键字大于pivotkey的记录，将其移动到high处。具体操作是：若low所指记录的值小于pivotkey，则向右移动指针low；否则移动该记录。重复步骤2和3，直至low和high。此时low和high的位置即为枢轴在此躺排序的最终位置，原表被分为两个子表。
代码实现
public class Sort {
public static void main(String
[] args
) {
int[] nums
= new int[]{1, 321, 34, 54, 56, 745, 7546,3,423,463,64,234,143421};
quickSort(nums
);
for (int n
: nums
) {
System
.out
.println(n
);
}
}
public static void quickSort(int[] nums
) {
qSort(nums
,0,nums
.length
- 1);
}
public static void qSort(int[] nums
,int low
,int high
) {
if(low
< high
) {
int pivotloc
= partition(nums
,low
,high
);
qSort(nums
,low
,pivotloc
- 1);
qSort(nums
,pivotloc
+1,high
);
}
}
public static int partition(int[] nums
,int low
,int high
) {
int pivotkey
= nums
[low
];
while (low
< high
) {
while (low
< high
&& nums
[high
] >= pivotkey
) { high
--; }
nums
[low
] = nums
[high
];
while (low
< high
&& nums
[low
] <= pivotkey
) { low
++;}
nums
[high
] = nums
[low
];
}
nums
[low
] = pivotkey
;
return low
;
}
}
