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

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

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,实现基本有序。

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.选择排序选择排序的思路是找出数组中的最小值,将其与数组的第一个元素交换位置。然后在剩余元素中找出最小值,将其与数组的第二个元素交换位置。如此反复,直到将整个数组排序。

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

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)将元素逆序输出得到有序序列。

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

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()这个步骤,它可以确保主元左边的值都比主元小,主元右边的值都比主元大。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！