快速排序是一种分而治之的算法。它基于这样的思想:选择一个元素作为主元，并围绕主元对数组进行分区，主元的左侧包含所有小于主元的元素，主元的右侧包含所有大于主元的元素。选择枢轴的方法有很多种。下面提到了其中的一些:
- 数组的第一个元素
- 数组的最后一个元素
- 数组的随机元素
- 数组的中位索引元素
与合并排序相比，快速排序的空间复杂度较低，因为它不使用辅助数组。
示例:
为了理解快速排序，让我们考虑一个未排序的数组 [-4, 1, 25, 50, 8, 10, 23] 并讨论对数组进行排序所采取的每个步骤升序排列。
在实现中在本例中，选择数组的最后一个元素作为主元。在分区过程开始时，创建变量i和j，它们最初是相同的。随着分区的进行，i 和 j 的值会变得不同。 i表示小于主元的元素和大于主元的元素之间的边界。 j表示大于pivot的元素和未分区数组之间的边界。
分区后生成两个分区，左侧分区包含小于pivot的元素，右侧分区包含大于pivot的元素。两个分区再次使用相同的逻辑进行分区，并且该过程继续进行，直到分区具有零个或一个元素。此过程的最终结果将是一个已排序的数组。
快速排序的实现
public class MyClass {
// 调用分区函数的快速排序函数
//根据枢轴元素排列和分割列表
//快速排序是一个递归函数
static void quicksort(int Array[], int left, int right) {
if (left < right) {
int pivot = partition(Array, left, right);
quicksort(Array, left, pivot-1);
quicksort(Array, pivot+1, right);
}
}
//分区函数排列和分割列表
//基于主元元素分成两个列表
// 在本例中，选择列表的最后一个元素
//作为枢轴元素。一个列表包含所有元素
//小于另一个列表包含的主元元素
//所有大于主元的元素
static int partition(int Array[], int left, int right) {
int i = left;
int pivot = Array[right];
int temp;
for(int j = left; j <=right; j++) {
if(Array[j] < pivot) {
temp = Array[i];
Array[i] = Array[j];
Array[j] = temp;
i++;
}
}
temp = Array[right];
Array[right] = Array[i];
Array[i] = temp;
return i;
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {-4, 1, 25, 50, 8, 10, 23};
int n = MyArray.length;
System.out.println("原始数组");
PrintArray(MyArray);
quicksort(MyArray, 0, n-1);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
-4 1 25 50 8 10 23
排序数组
-4 1 8 10 23 25 50 时间复杂度:
最坏情况下快速排序的时间复杂度为θ(N²)，最佳和平均情况下的时间复杂度为θ(NlogN) .