Java数据结构之基于比较的排序算法基本原理及具体实现

2023年5月17日上午4:51 • 数据结构

Java数据结构之基于比较的排序算法基本原理及具体实现

前言

排序算法是计算机科学中最基本的算法之一，其广泛应用于各领域中。基于比较的排序算法是一种流行的排序算法类型，本篇文章将阐述其基本原理及具体实现，以帮助读者深入了解该算法。

算法介绍

基于比较的排序算法是根据元素之间的比较操作来完成排序的一种算法类型，它可以对各种数据类型进行排序，如整数、浮点数、字符串等。此类算法的核心思想是比较两个元素的大小，再根据比较结果进行元素位置的调整。

常见的基于比较的排序算法有冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序等。

以下着重介绍冒泡排序、快速排序两种排序算法。

冒泡排序

冒泡排序是一种简单的排序算法，它反复遍历要排序的数列，每次比较相邻两个元素的大小，如果顺序错误，就把它们交换过来，扫描数列的工作是重复进行的，直到数列没有任何交换为止。

冒泡排序的整个过程可以概括为：

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
遍历所有元素，重复步骤1；
重复上述步骤N遍，直到排序完成。

示例代码：

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len-1; i++) {
        boolean flag = false;
        for (int j = 0; j < len-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = true;
            }
        }
        if (!flag)
            break;
    }
}

快速排序

快速排序是基于分治法的高效排序算法，它选择一个主元素（pivot），将小于主元素的元素放在它的左侧，大于主元素的元素放在它的右侧。接着，针对左侧和右侧的元素分别进行快速排序，直到排序完成。

快速排序的整个过程可以概括为：

如果数组长度为1，则返回；
选择一个主元素pivot；
将小于pivot的元素放在其左侧，大于pivot的元素放在其右侧；
递归地对左侧和右侧的元素分别进行快速排序。

示例代码：

public static void quickSort(int[] arr, int begin, int end) {
    if (begin >= end)
        return;
    int pivotIndex = partition(arr, begin, end);
    quickSort(arr, begin, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
}

public static int partition(int[] arr, int begin, int end) {
    int pivot = arr[end];
    int i = begin - 1;
    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[end];
    arr[end] = temp;
    return i + 1;
}