当前位置: 首页 > >

【Java】实现快排算法

发布时间:

一:快排算法简述
快速排序是一种排序执行效率很高的排序算法,它利用分治法来对待排序序列进行分治排序,它的思想主要是通过一趟排序将待排记录分隔成独立的两部分,其中的一部分比关键字小,后面一部分比关键字大,然后再对这前后的两部分分别采用这种方式进行排序,通过递归的运算最终达到整个序列有序,下面我们简单进行阐述。


二:快排思路
我们从一个数组来逐步逐步说明快速排序的方法和思路。



假设我们对数组{7, 1, 3, 5, 13, 9, 3, 6, 11}进行快速排序。
1:首先在这个序列中找一个数作为基准数,为了方便可以取第一个数。
2:遍历数组,将小于基准数的放置于基准数左边,大于基准数的放置于基准数右边
3:此时得到类似于这种排序的数组{3, 1, 3, 5, 6, 7, 9, 13, 11}。
4: 在初始状态下7是第一个位置,现在需要把7挪到中间的某个位置k,也即k位置是两边数的分界点。
5:那如何做到把小于和大于基准数7的值分别放置于两边呢,我们采用双指针法,从数组的两端分别进行比对
6:先从最右位置往左开始找直到找到一个小于基准数的值,记录下该值的位置(记作 i)。
7:再从最左位置往右找直到找到一个大于基准数的值,记录下该值的位置(记作 j)。
8: 如果位置i9:如果执行到i==j,表示本次比对已经结束,将最后i的位置的值与基准数做交换,此时基准数就找到了临界点的位置k,位置k两边的数组都比当前位置k上的基准值或都更小或都更大。
10:上一次的基准值7已经把数组分为了两半,基准值7算是已归位(找到排序后的位置)。
11:通过相同的排序思想,分别对7两边的数组进行快速排序,左边对[left, k-1]子数组排序,右边则是[k+1, right]子数组排序。
12:利用递归算法,对分治后的子数组进行排序。
13:快速排序之所以比较快,是因为相比冒泡排序,每次的交换都是跳跃式的,每次设置一个基准值,将小于基准值的都交换到左边,大于基准值的都交换到右边,这样不会像冒泡一样每次都只交换相邻的两个数,因此比较和交换的此数都变少了,速度自然更高。当然,也有可能出现最坏的情况,就是仍可能相邻的两个数进行交换。



快速排序基于分治思想,它的时间*均复杂度很容易计算得到为O(NlogN)。


三:代码实现


import java.util.Arrays;

public class quicksort {
public static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static int partion(int[] arr,int left, int right){
int key=arr[left];
int start=left;
while (left
//一定要从后往前找第一个小于key的位置,否则数据的位置会产生错误
while (left=key){
right--;
}
//从前向后找第一个大于key的数据位置
while (left
left++;
}
//交换
swap(arr,left,right);
}
//把基准值和相遇的位置的数据进行交换
//错误: arr[left] = key; 相遇位置的数据被覆盖
swap(arr,left,start);
return left;

}
public static void quickSort(int[] array,int left,int right){
if(left
int mid =partion(array,left,right);//获取基准值在第一次排序后的下标位置
quickSort(array,left,mid-1);//分为左右两个组再进行排序,递归
quickSort(array,mid+1,right);
}

}
public static void main(String[] args) {
int[] array={1,4,5,3,7,8,8,9};
int left=0;
int right=array.length-1;
quickSort(array,left,right);
System.out.println(Arrays.toString(array));
}
}



友情链接: