Java快排入门(面试常见问题)
快速排序算法是最常用的排序算法之一,尤其是对大型列表/数组进行排序。快速排序是一种分而治之算法,这意味着原始数组被分成两个数组,每个数组单独排序,然后合并排序输出以生成排序数组。平均而言,它具有O(n log n)复杂性,使快速排序适用于对大数据卷进行排序。
用更标准的话来说,快速排序算法通过与元素进行比较,将未排序的部分反复划分为低阶子节和高阶子节。在递归结束时,我们得到排序数组。请注意,快速排序可以用于“就地”排序。这意味着排序在数组中进行,不需要创建其他数组。pivot
快速排序算法
快速排序算法的基本思想可以描述为以下步骤:
如果数组仅包含一个元素或零个元素,则对数组进行排序。如果数组包含多个元素,则:
- 选择一个元素作为枢轴元素,通常从中间开始,但不是必需的。
- 数据元素分为两部分:一部分包含比枢轴元素顺序低的元素,另一部分包含比枢轴元素顺序更高的元素。
- 通过重复步骤 1 和 2 分别对这两个部分进行排序。
快速排序 Java 示例
下面是快速排序 Java 实现示例。
public class QuickSortExample
{
public static void main(String[] args)
{
// 下面是一个无序的数组
Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
// 使用快排来给他排序
quickSort( array, 0, array.length - 1 );
// 输出并验证排序结果
System.out.println(Arrays.toString(array));
}
public static void quickSort(Integer[] arr, int low, int high)
{
//检查空数组
if (arr == null || arr.length == 0){
return;
}
if (low >= high){
return;
}
//从列表中间获取pivot元素
int middle = low + (high - low) / 2;
int pivot = arr[middle];
// 让 left < pivot 并且 right > pivot
int i = low, j = high;
while (i <= j)
{
//检查左侧数组上的所有值是否低于pivot
while (arr[i] < pivot)
{
i++;
}
//检查直到左侧数组上的所有值都大于pivot
while (arr[j] > pivot)
{
j--;
}
//现在比较列表两边的值,看看它们是否需要交换
//交换后,在两个列表上移动迭代器
if (i <= j)
{
swap (arr, i, j);
i++;
j--;
}
}
//递归地执行与上面相同的操作以对两个子数组进行排序
if (low < j){
quickSort(arr, low, j);
}
if (high > i){
quickSort(arr, i, high);
}
}
public static void swap (Integer array[], int x, int y)
{
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
执行输出结果:
[3, 6, 10, 12, 13, 24, 70, 90]
在 Java 中,
Arrays.sort()
方法使用快速排序算法对使用双pivot元素的原语数组进行排序。双pivot使该算法更加快速。