快速排序算法的核心思想是分治法(Divide and Conquer)。
快速排序算法通过以下步骤实现排序:
1. 选择基准值 : 从数列中选择一个元素作为基准值(pivot),通常选择第一个元素。
2. 分区操作 : 重新排列数列,使得所有小于基准值的元素都移到基准的前面,而所有大于基准值的元素都移到基准的后面。这一步完成后,基准值就处于其最终位置。
3. 递归排序 : 递归地将小于和大于基准值的子数列进行快速排序。
在每次分区过程中,至少有一个元素被放置在其最终位置,这保证了算法的收敛性。快速排序的平均时间复杂度为O(n log n),但在最坏情况下可以退化到O(n^2)。尽管如此,由于其高效、就地排序(不需要额外存储空间)的特点,快速排序通常被认为是实践中最有效的通用排序算法之一。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void quickSort(int[] arr, int l, int r){
if(l >= r){
return;
}
//必须固定值,不可固定位置,毕竟这个位置的值会发生变化
int mid = arr[l + r >> 1];
int i = l -1, j = r + 1;
// 左右区间交换位置,让左边区间的值都小于mid,右边区间的值都大于mid
while (i mid){};
if (i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net