十大经典排序算法视频讲解

on 2019-09-16 | by Hawstein's Blog 关注作者

代码仓库

代码仓库包含了完整的代码实现和测试，其中 Java 版本是官方实现，其他语言版本来自社区贡献。对于每一种排序算法，如果有多种实现方法，都会尽量提供。另外代码仓库中还提供了完备的测试用例，以此确保实现的排序算法覆盖了每一种可能的情况。

GitHub 链接：https://github.com/HawsteinStudio/algocasts-sorting-algorithms

冒泡排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/AEpoDvWQ

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class BubbleSort {

  private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  // Time: O(n^2), Space: O(1)
  public void sort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    for (int end = n-1; end > 0; --end) {
      for (int i = 0; i < end; ++i) {
        if (arr[i] > arr[i+1]) {
          int tmp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = tmp;
        }
      }
    }
  }

  // Time: O(n^2), Space: O(1)
  public void sortShort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    for (int end = n-1; end > 0; --end)
      for (int i = 0; i < end; ++i)
        if (arr[i] > arr[i+1])
          swap(arr, i, i+1);
  }

  // Time: O(n^2), Space: O(1)
  public void sortEarlyReturn(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    boolean swapped;
    for (int end = n-1; end > 0; --end) {
      swapped = false;
      for (int i = 0; i < end; ++i) {
        if (arr[i] > arr[i+1]) {
          swap(arr, i, i+1);
          swapped = true;
        }
      }
      if (!swapped) return;
    }
  }

  // Time: O(n^2), Space: O(1)
  public void sortSkip(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    int newEnd;
    for (int end = n-1; end > 0;) {
      newEnd = 0;
      for (int i = 0; i < end; ++i) {
        if (arr[i] > arr[i+1]) {
          swap(arr, i, i+1);
          newEnd = i;
        }
      }
      end = newEnd;
    }
  }

}

选择排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/Z5mzdwpd

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class SelectionSort {

  private void swap(int[] arr, int i, int j) {
    if (i == j) return;
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  // Time: O(n^2), Space: O(1)
  public void sort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    for (int i = 0; i < n; ++i) {
      int minIdx = i;
      for (int j = i+1; j < n; ++j)
        if (arr[j] < arr[minIdx])
          minIdx = j;
      swap(arr, i, minIdx);
    }
  }

  // Time: O(n^2), Space: O(1)
  public void sortFromEnd(int[] arr) {
    if (arr == null || arr.length == 0) return;
    int n = arr.length;
    for (int i = n-1; i > 0; --i) {
      int maxIdx = i;
      for (int j = 0; j < i; ++j)
        if (arr[j] > arr[maxIdx])
          maxIdx = j;
      swap(arr, i, maxIdx);
    }
  }

}

插入排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/dbGY9eG5

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class InsertionSort {

  // Time: O(n^2), Space: O(1)
  public void sort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    for (int i = 1; i < arr.length; ++i) {
      int cur = arr[i];
      int j = i - 1;
      while (j >= 0 && arr[j] > cur) {
        arr[j+1] = arr[j];
        --j;
      }
      arr[j+1] = cur;
    }
  }

}

希尔排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/zbmKZgWZ

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ShellSort {

  // Time: O(n^2), Space: O(1)
  public void sort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    for (int gap = arr.length>>1; gap > 0; gap >>= 1) {
      for (int i = gap; i < arr.length; ++i) {
        int cur = arr[i];
        int j = i - gap;
        while (j >= 0 && arr[j] > cur) {
          arr[j+gap] = arr[j];
          j -= gap;
        }
        arr[j+gap] = cur;
      }
    }
  }

  // Time: O(n^2), Space: O(1)
  public void insertionSort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    for (int i = 1; i < arr.length; ++i) {
      int cur = arr[i];
      int j = i - 1;
      while (j >= 0 && arr[j] > cur) {
        arr[j + 1] = arr[j];
        j -= 1;
      }
      arr[j + 1] = cur;
    }
  }

}

快速排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/kVG9Pxmg

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class QuickSort {

  private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  // [ ... elem < pivot ... | ... elem >= pivot ... | unprocessed elements ]
  //                          i                       j
  private int lomutoPartition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; ++j) {
      if (arr[j] < pivot) {
        swap(arr, i, j);
        ++i;
      }
    }
    swap(arr, i, high);
    return i;
  }

  // lomuto partition 的另一种实现，可以把最后的 swap 合并到循环中。
  private int lomutoPartition2(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j <= high; ++j) {
      if (arr[j] <= pivot) {
        swap(arr, i, j);
        ++i;
      }
    }
    return i-1;
  }

  private void lomutoSort(int[] arr, int low, int high) {
    if (low < high) {
      int k = lomutoPartition(arr, low, high);
      lomutoSort(arr, low, k-1);
      lomutoSort(arr, k+1, high);
    }
  }

  private int hoarePartitionDoWhile(int[] arr, int low, int high) {
    int pivot = arr[low + (high-low)/2];
    int i = low-1, j = high+1;
    while (true) {
      do {
        ++i;
      } while (arr[i] < pivot);
      do {
        --j;
      } while (arr[j] > pivot);
      if (i >= j) return j;
      swap(arr, i, j);
    }
  }

  // [ ... elem <= pivot ... | unprocessed elements | ... elem >= pivot ... ]
  //                         i                      j
  private int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low + (high-low)/2];
    int i = low, j = high;
    while (true) {
      while (arr[i] < pivot) ++i;
      while (arr[j] > pivot) --j;
      if (i >= j) return j;
      swap(arr, i++, j--);
    }
  }

  private void hoareSort(int[] arr, int low, int high) {
    if (low < high) {
      int k = hoarePartition(arr, low, high);
      hoareSort(arr, low, k);
      hoareSort(arr, k+1, high);
    }
  }

  // Time: O(n*log(n)), Space: O(n)
  public void lomutoSort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    lomutoSort(arr, 0, arr.length-1);
  }

  // Time: O(n*log(n)), Space: O(n)
  public void hoareSort(int[] arr) {
    if (arr == null || arr.length == 0) return;
    hoareSort(arr, 0, arr.length-1);
  }

}

归并排序

视频链接：https://algocasts.io/series/sorting-algorithms/episodes/M0G2k7pz

截图：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class MergeSort {

  // sorted sub-array 1: arr[low ... mid]
  // sorted sub-array 2: arr[mid+1 ... high]
  private void merge(int[] arr, int low, int mid, int high, int[] tmp) {
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
      else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= high) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, low, k);
  }

  private void mergeSort(int[] arr, int low, int high, int[] tmp) {
    if (low < high) {
      int mid = low + (high - low) / 2;
      mergeSort(arr, low, mid, tmp);
      mergeSort(arr


                
                    文章来源：
                    Author：Hawstein's Blog
link：http://hawstein.com/2019/09/16/sorting-algorithms-episodes/


            
                下一篇：AlgoCasts 2019 年 8 月小结
                上一篇：AlgoCasts 2019 年 7 月小结

十大经典排序算法视频讲解

代码仓库

冒泡排序

选择排序

插入排序

希尔排序

快速排序

归并排序

添加我喜欢的博客

编辑我的关注

更多推荐博客

十大经典排序算法视频讲解

代码仓库

冒泡排序

选择排序

插入排序

希尔排序

快速排序

归并排序

添加我喜欢的博客

编辑 我的关注

更多 推荐博客

编辑我的关注

更多推荐博客