深入了解快速排序算法

简介: 深入了解快速排序算法

快速排序(Quick Sort)是一种高效的、分治法的排序算法,它在实际应用中被广泛采用,因为其性能优越。本文将详细介绍快速排序的工作原理,提供示例和Python、Go、Java以及C语言的实现代码。


快速排序的基本思想


快速排序的核心思想是通过选择一个基准元素,将数组划分为两个子数组:小于基准的子数组和大于基准的子数组。然后,递归地对这两个子数组进行排序,最后将它们合并起来,完成整个排序过程。


以下是快速排序的详细步骤:

1.选择基准元素: 从待排序的数组中选择一个基准元素。通常,我们选择第一个元素,但也可以使用其他策略,如随机选择。

2.划分数组: 将数组中的元素按照与基准元素的比较结果划分为两个子数组,一个包含小于基准的元素,另一个包含大于基准的元素。

3.递归排序: 对划分后的子数组递归地应用快速排序算法,分别排序小于基准的子数组和大于基准的子数组。

4.合并结果: 最后,将已排序的子数组合并起来,形成最终有序的数组。


快速排序的关键在于划分步骤,也就是如何选择基准元素和将元素分配到子数组的过程。这一过程的高效性使得快速排序在大多数情况下表现出色。


快速排序的示例


让我们通过一个示例来理解快速排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4],我们希望按升序排序它。

1.选择基准元素: 我们选择第一个元素 5 作为基准。

2.划分数组: 我们遍历数组并将小于等于基准的元素放在左边,大于基准的元素放在右边。在这个示例中,划分后的结果是 [2, 3, 4] [5] [9]。

3.递归排序: 我们对左边的子数组 [2, 3, 4] 和右边的子数组 [9] 分别应用快速排序。

4.合并结果: 最终,将左边的子数组 [2, 3, 4]、基准元素 5 和右边的子数组 [9] 合并起来,得到 [2, 3, 4, 5, 9],这就是排序后的数组。


快速排序的时间复杂度


快速排序通常具有较快的平均运行时间,并且在许多情况下表现优异。其平均时间复杂度为O(n*log(n)),其中n是数组的长度。在最坏情况下,时间复杂度为O(n^2),但这种情况较少发生,并且通过随机选择基准元素或使用三取样划分等方法可以避免。


与其他排序算法相比,快速排序通常更快,尤其是在处理大型数据集时。它是许多标准库中的默认排序算法,如Python的sorted()函数和Java的Arrays.sort()方法。


示例代码


以下是快速排序的示例代码,分别使用Python、Go、Java和C语言编写。

Python 快速排序


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
        
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    
    return quick_sort(less) + [pivot] + quick_sort(greater)
    
arr = [5, 2, 9, 3, 4]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)


Go 快速排序


package main

import "fmt"

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    pivot := arr[0]
    var less, greater []int
    
    for _, v := range arr[1:] {
        if v <= pivot {
            less = append(less, v)
        } else {
            greater = append(greater, v)
        }
    }
    
    less = quickSort(less)
    greater = quickSort(greater)
    
    return append(append(less, pivot), greater...)
}

func main() {
    arr := []int{5, 2, 9, 3, 4}
    sorted_arr := quickSort(arr)
    fmt.Println("排序后的数组:", sorted_arr)
}


Java 快速排序


import java.util.Arrays;

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int left = low + 1;
        int right = high;
        
        while (true) {
            while (left <= right && arr[left] <= pivot) {
                left++;
            }
            while (left <= right && arr[right] >= pivot) {
                right--;
            }
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            } else {
                break;
            }
        }
        
        int temp = arr[low];
        arr[low] = arr[right];
        arr[right] = temp;
        
        return right;
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}


C 语言 快速排序


#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int left = low + 1;
    int right = high;
    
    while (1) {
        while (left <= right && arr[left] <= pivot) {
            left++;
        }
        while (left <= right && arr[right] >= pivot) {
            right--;
        }
        if (left <= right) {
            swap(&arr[left], &arr[right]);
        } else {
            break;
        }
    }
    
    swap(&arr[low], &arr[right]);
    return right;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}


以上示例代码展示了不同编程语言中的快速排序算法实现。这些示例帮助你理解快速排序的工作原理,并提供了可供参考和使用的代码示例。无论使用哪种编程语言,快速排序都是一种高效的排序算法,适用于各种应用场景。


目录
打赏
0
2
2
0
105
分享
相关文章
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
84 4
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
153 61
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
84 1
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
50 0
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
71 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
81 3
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
66 3

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等