六大排序算法:插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

2023-06-26 11:45:39 浏览数 (2)

1.插入排序插入排序的思路是将数组分成已排序区间和未排序区间。初始已排序区间只有一个元素,然后一次插入未排序区间的元素到已排序区间中,直到全部元素插入已排序区间。

代码语言:javascript复制
java
public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i  ) {
        int value = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > value) {
            arr[j   1] = arr[j];
            j--;
        }
        arr[j   1] = value;
    }
}

该算法的时间复杂度为O(n2),空间复杂度为O(1)。插入排序适用于 already sorted 或几乎已经排序的数据。2.希尔排序 希尔排序通过交换不相邻元素来实现排序,其目的是让数组中任意间隔为h的元素都是有序的。此时数组的性能接近O(n)。然后h逐渐缩小至1,实现基本有序。

代码语言:javascript复制
java
public void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i  ) {
            int j = i;
            int temp = arr[i];
            while (j - gap >= 0 && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = temp;
        }
    }
}  

该算法的最优时间复杂度为O(n),最差时间复杂度为O(n2)。空间复杂度为O(1)。Shell排序适用于大规模数据的排序。3.选择排序选择排序的思路是找出数组中的最小值,将其与数组的第一个元素交换位置。然后在剩余元素中找出最小值,将其与数组的第二个元素交换位置。如此反复,直到将整个数组排序。

代码语言:javascript复制
java
public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i  ) {
        int minIndex = i;
        for (int j = i   1; j < n; j  ) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
} 

该算法的时间复杂度和空间复杂度均为O(n2)。选择排序的优点在于数据移动是最少的,但是如果数据量较大,排序速度较慢。

4.冒泡排序冒泡排序的思路是比较相邻的元素,如果顺序错误就把元素交换过来。它从第一个元素开始,比较相邻元素,如果第一个比第二个大,就交换二者位置。然后比较第二个和第三个,以此类推。这样 一趟下来,最后的元素就是最大值或最小值。

代码语言:javascript复制
java 
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i  ) {
        for (int j = 0; j < arr.length - 1 - i; j  ) {
            if (arr[j] > arr[j   1]) {
                int temp = arr[j];
                arr[j] = arr[j   1];
                arr[j   1] = temp;
            }
        }
    } 
} 

冒泡排序的时间复杂度与空间复杂度均为O(n2)。冒泡排序不是很高效,但简单易理解,可以在非常短时间内完成排序。5.堆排序堆排序使用二叉堆数据结构来实现。其步骤如下:1)将数组构造成二叉大顶堆(每个节点的值都大于其左右节点的值) 2)将堆顶元素和最后一个元素交换 3)将剩余的堆元素再次构造成二叉堆,并重复步骤2,直到大顶堆元素个. 4)将元素逆序输出得到有序序列。

代码语言:javascript复制
java
public void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) return;
    for (int i = 0; i < arr.length; i  ) {
        // 从第一个非叶子节点从下至上,从右至左调整结构
        adjustHeap(arr, i, arr.length); 
    }
    // 调整堆结构后,堆顶元素与末尾元素交换,并从堆顶元素开始重复调整堆
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        adjustHeap(arr, 0, i);
    }
}

public void adjustHeap(int[] arr, int i, int length) {
    int temp = arr[i];
    // 定位左孩子结点和右孩子结点
    for (int k = i * 2   1; k < length; k = k * 2   1) {
        if (k   1 < length && arr[k] < arr[k   1]) {  // 右孩子结点的值大于左孩子结点的值
            k  ; 
        }
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)。堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换,此时末尾就为最大值。 然后将剩余元素重新构造成大顶堆,这样做n-1次,就完成了整个序列的排序。

6.快速排序快速排序使用分治法来把一个数组分为两个子数组,其步骤如下:1)从数组中挑出一个元素作为基准(pivot),通常选择第一个、最后一个或中间一个元素。2)分割:所有比基准值小的元素挪到基准前面,所有比基准值大的元素挪到基准后面。3)递归地对基准值前后的两个子数组进行快速排序,直到数组已经完全排序。```java

代码语言:javascript复制
public void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quick quickSort(arr, pivot   1, right);
    }
}

public int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left;
    int j = right;
    while (i < j) {
        while (arr[i] <= pivot && i < right)
            i  ;
        while (arr[j] > pivot && j > left)
            j--;
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[j];
    arr[j] = pivot;
    return j;
}

快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn)。快速排序思想简单但实现比较巧妙,是常用的高效排 序算法。快速排序采用分治法策略,以第一个元素为主元,将数组分成两半,左半部的值都比主元小,右半部的值都比主元大。然后递归地排序两个子数组。快速排序最重要的是partition()这个步骤,它可以确保主元左边的值都比主元小,主元右边的值都比主元大。

0 人点赞