快速排序算法
步骤:1.先在数组元素中选出一个基准值(pivot)(比较值)
2.将数组中大于基准值(pivot)的元素统一移到基准值右边
将数组中小于基准值(pivot)的元素统一移到基准值左边
3.用递归的方式分别对基准值(pivot)左右两边的子序列重复前两步操作,完成快速排序
基本思路:一般选择将待排序序列分为两个序列,正中间的那个数作为关键字,然后两个指针一个从头到关键字遍历,遇到大于(小于)关键字的元素就停下来,另一个指针从尾到关键字遍历,遇到小于(大于)关键字的元素停下来,交换两个指针的元素完成排序;将序列递归分治按照前面的原理排序,直到序列有序。
平均时间复杂度:O(nlogn)
1.main方法调用排序算法对数组进行排序
public class QuickSort {
private static int count;
public static void main(String[] args) {
int[] arr = {3, 45, 78, 99, 45, 11, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49};
System.out.println("未排序的数组:" + Arrays.toString(arr));
quickSort01(arr, 0, arr.length - 1);
System.out.println("排序的数组:" + Arrays.toString(arr));
}
快速排序算法(以中间元素为基准)
/**
* 快速排序算法(以中间元素为基准)
* @param arr 排序的数组
* @param left 左指针
* @param right 右指针
*/
private static void quickSort01(int[] arr,int left,int right){
int l = left;
int r = right;
int pivot = arr[(left+right)/2];//选取数组中间元素作为基准
int temp = 0;//temp作为中间转换变量
while (l<r) {
while (arr[l] < pivot) {//当左元素小于基准时,就往右进一位
l++;
}
while (arr[r] > pivot) {//当右元素大于基准时,就往左进一位
r--;
}
if (l >= r) {//当两个指针指向同一个位置时,就跳出循环
break;
}
//交换值,左指针所指大于基准值的与右指针所指小于基准值的交换位置
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == pivot) {//如果左指针指向元素的值等于基准值,右指针往左移动一格
r--;
}
if (arr[r] == pivot) {//如果右指针指向元素的值等于基准值,左指针往右移动一格
l++;
}
}
//第一次排序结束后,用递归的方式,
//开始对基准值两边的元素开始排序
if (l==r){
l++;
r--;
}
if (left<r){
quickSort01(arr,left,r);
}
if (l<right){
quickSort01(arr,l,right);
}
}
3.快速排序算法(以第一个元素为基准)
/**
* 快速排序算法(以第一个元素为基准)
* @param arr 排序的数组
* @param left 数组的第一个元素索引
* @param right 数组的最后一个元素索引
*/
private static void quickSort02(int[] arr,int left,int right){
if (left >= right){
//递归退出条件
return;
}
int l = left;//l为数组的左指针
int r = right;//r为数组的右指针
while (l<r){
while (l<r && arr[r]>=arr[left]) {//如果右指针所指元素大于基准数,就往左移动
r--;
}
while (l<r && arr[l]<=arr[left]){//如果左指针所指元素小于基准数,就往右移动
l++;
}
if (l == r){//如果两个指针指向同一个元素,就将此元素与第一个元素对调位置
int temp = arr[left];
arr[left] = arr[r];
arr[r] = temp;
}else{//如果两个指针没有指向同一个位置,就将两个指针所指向的元素对调位置
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
QuickSort.count++;//计算排序总共调用用了多少次
}
quickSort02(arr,left,l-1);//递归方式对基数左边的数进行排序
quickSort02(arr,r+1,right);//递归方式对基数右边的数进行排序
}
}
还没有评论,来说两句吧...