插入，选择，堆，极快排序算法思想和复杂度

目录

插入排序

思想

算法步骤

代码

复杂度

选择排序

思想

算法步骤

代码

复杂度

堆排序 

思想

算法步骤

代码

复杂度

 快速排序

 思想

算法步骤

代码

复杂度

稳定性

---

插入排序

思想

插入排序是一种简单直观的排序算法。它的工作原理是将数组分为已排序和未排序两部分，然后依次将未排序元素插入到已排序部分的正确位置，直至整个数组排序完成。

算法步骤

1.从第一个元素开始，将其视为已排序部分

2.取出下一个元素，在已排序部分从后向前进行比较，找到合适的位置并插入

3.重复上述步骤，直到所有元素都被插入到已排序部分。

代码

1.  
   public static void insertSort(int[] array) {
2.  
   for (int i = 1; i < array.length; i ) {
3.  
   int tmp = array[i];
4.  
   int j = i - 1;
5.  
   for (; j >= 0; j--) {
6.  
   if(tmp < array[j]) {
7.  
   array[j 1] = array[j];
8.  
   }else {
9.  
   break;
10.  
    }
11.  
    }
12.  
    array[j 1] = tmp;
13.  
    }
14.  
    }

复杂度

• 最坏情况时间复杂度：O(n^2) （数组完全逆序）
• 最好情况时间复杂度：O(n) （数组已经有序）
• 平均情况时间复杂度：O(n^2)
• 空间复杂度：O(1) （原地排序）

---

选择排序

思想

选择排序也是一种简单的排序算法。它的主要思想是每次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾，逐步形成有序序列。

算法步骤

1.从数组中找到最小元素，将其与第一个元素交换位置，将第一个元素视为已排序部分。

2.从剩余的未排序部分中找到最小元素，将其与第二个元素交换位置，将前两个元素视为已排序部分。

3.重复上述步骤，直到所有元素都排序完成。

代码

1.  
   public static void selectSort(int[] array) {
2.  
   for (int i = 0; i < array.length; i ) {
3.  
   int min = i;
4.  
   for (int j = i 1; j < array.length; j ) {
5.  
   if (array[j] < array[min]) {
6.  
   min = j;
7.  
   }
8.  
   }
9.  
   swap(array, i, min);
10.  
    }
11.  
    }
12.  
     
13.  
     
14.  
    private static void swap(int[] array, int i, int min) {
15.  
    int tmp = array[i];
16.  
    array[i] = array[min];
17.  
    array[min] = tmp;
18.  
    }

复杂度

• 最坏情况时间复杂度：O(n^2)
• 最好情况时间复杂度：O(n^2)
• 平均情况时间复杂度：O(n^2)
• 空间复杂度：O(1) （原地排序）

---

堆排序 

思想

堆排序是一种高效的排序算法，利用了二叉堆的数据结构。它通过构建最大堆（升序排序时使用）或最小堆（降序排序时使用）来进行排序。

算法步骤

1.将输入数组构建成一个二叉堆。

2.不断从堆顶取出最大（或最小）元素，放入已排序部分的末尾，并调整堆保持其性质。

3.重复上述步骤，直到所有元素都被取出，形成有序序列。

代码

1.  
   public static void heapSort(int[] array) {
2.  
   createBigHeap(array);
3.  
   int end = array.length - 1;
4.  
   while (end > 0) {
5.  
   swap(array,0,end);
6.  
   siftDown(array,0,end);
7.  
   end--;
8.  
   }
9.  
   }
10.  
     
11.  
    private static void createBigHeap(int[] array) {
12.  
    for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {
13.  
    siftDown(array,parent,array.length);
14.  
    }
15.  
    }
16.  
     
17.  
    private static void siftDown(int[] array, int parent, int end) {
18.  
    int child = parent*2 1;
19.  
    while (child < end) {
20.  
    if(child 1 < end && array[child] < array[child 1]) {
21.  
    child ;
22.  
    }
23.  
    if (array[child] > array[parent]){
24.  
    swap(array,child,parent);
25.  
    parent = child;
26.  
    child = parent*2 1;
27.  
    }else {
28.  
    break;
29.  
    }
30.  
    }
31.  
    }

复杂度

• 最坏情况时间复杂度：O(n log n)
• 最好情况时间复杂度：O(n log n)
• 平均情况时间复杂度：O(n log n)
• 空间复杂度：O(1) （原地排序）

---

 快速排序

 思想

快速排序是一种常用且高效的排序算法，它采用了分治的思想。快速排序的核心在于选取一个基准元素，将数组分为左右两个子数组，使得左边的元素都小于等于基准，右边的元素都大于等于基准，然后对子数组递归地进行快速排序。

算法步骤

1.选择一个基准元素（通常为数组的第一个或最后一个元素）。

2.将数组分成两个子数组，使得左边子数组的元素都小于等于基准，右边子数组的元素都大 于等于基准。

3.对左右子数组递归地进行快速排序。

4.将左边子数组、基准元素和右边子数组合并成最终的有序数组。

代码

1.  
   public static void quickSort(int[] array) {
2.  
   quick(array,0,array.length-1);
3.  
   }
4.  
    
5.  
   private static void quick(int[] array, int start, int end) {
6.  
   if(start >= end) {
7.  
   return;
8.  
   }
9.  
   int pivot = partition(array,start,end);
10.  
    quick(array,start,pivot-1);
11.  
    quick(array,pivot 1,end);
12.  
    }
13.  
     
14.  
    //挖坑法
15.  
    private static int partition(int[] array, int start, int end) {
16.  
    int key = array[start];
17.  
    while (start < end) {
18.  
    while (start < end && array[end] >= key) {
19.  
    end--;
20.  
    }
21.  
    array[start] = array[end];
22.  
    while (start < end && array[start 1] <= key) {
23.  
    start ;
24.  
    }
25.  
    array[end] = array[start];
26.  
    }
27.  
    array[start] = key;
28.  
    return start;
29.  
    }

复杂度

• 最坏情况时间复杂度：O(n^2) （基准选取不当导致）
• 最好情况时间复杂度：O(n log n) （每次都能将数组平衡地分割）
• 平均情况时间复杂度：O(n log n)
• 空间复杂度：O(log n) （递归调用栈的深度

---

稳定性

稳定的排序：插入排序，选择排序

不稳定排序：快速排序，堆排序

这篇好文章是转载于：学新通技术网