十大经典排序算法介绍与实现(Java/C++)

BCwzmhtDvNU21PH

引言

排序算法是计算机科学与工程中最基础也最重要的算法之一。一个优秀的程序员必须深刻理解各种排序算法的原理、实现、优劣与应用场景。本文将详细介绍十种经典排序算法,并给出Java与C++的代码实现,旨在为读者全面梳理排序算法,夯实算法基本功。

1. 冒泡排序(Bubble Sort)

1.1 算法原理

冒泡排序重复遍历要排序的数列,每次比较两个元素,如果顺序错误就把它们交换过来。遍历数列的工作重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。

1.2 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

1.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

1.4 复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

2. 选择排序(Selection Sort)

2.1 算法原理

选择排序每次从未排序部分选出最小元素,然后放到已排序部分的末尾。重复这个过程,直到所有元素均排序完毕。

2.2 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

2.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort(int arr[], int n) {
    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[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp; 
    }
}

2.4 复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

3. 插入排序(Insertion Sort)

3.1 算法原理

插入排序将数组分为”已排序”和”未排序”两部分,依次从”未排序”部分取出元素,在”已排序”部分中找到合适的位置插入。

3.2 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
public void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

3.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

3.4 复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

4. 希尔排序(Shell Sort)

4.1 算法原理

希尔排序是插入排序的改进版。它通过比较相距一定间隔的元素来进行,各趟比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。

4.2 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

4.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

4.4 复杂度分析

  • 时间复杂度:O(n log n) ~ O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

5. 归并排序(Merge Sort)

5.1 算法原理

归并排序采用分治法(Divide and Conquer)策略。它将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案”修补”在一起。

5.2 Java实现

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
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
 
    int[] L = new int[n1];
    int[] R = new int[n2];
 
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j]; 
    }
 
    int i = 0, j = 0;
 
    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

5.3 C++实现

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
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
 
    int L[n1], R[n2];
 
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
 
    int i = 0, j = 0;
 
    int k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
 
        merge(arr, left, mid, right);
    }
}

5.4 复杂度分析

  • 时间复杂度:O(n log n)
  • 空间复杂度:O(n)
  • 稳定性:稳定

6. 快速排序(Quick Sort)

6.1 算法原理

快速排序选择一个基准元素,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。

6.2 Java实现

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
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
 
    for(int j = low; j <= high - 1; 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[high];
    arr[high] = temp;
    return (i + 1);
}

6.3 C++实现

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
int partition (int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
 
    for (int j = low; j <= high - 1; 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[high];
    arr[high] = temp;
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

6.4 复杂度分析

  • 时间复杂度:平均O(n log n),最坏O(n^2)
  • 空间复杂度:O(log n)
  • 稳定性:不稳定

7. 堆排序(Heap Sort)

7.1 算法原理

堆排序利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

7.2 Java实现

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
public void heapSort(int[] arr) {
    int n = arr.length;
 
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
 
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
 
        heapify(arr, i, 0);
    }
}
 
void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
 
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
 
        heapify(arr, n, largest);
    }
}

7.3 C++实现

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
void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1; 
    int r = 2*i + 2;
 
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
 
    for (int i=n-1; i>0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

7.4 复杂度分析

  • 时间复杂度:O(n log n)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

8. 计数排序(Counting Sort)

8.1 算法原理

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

8.2 Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void countSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    int[] count = new int[range];
    int[] output = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }
 
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
 
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
 
    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

8.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void countSort(int arr[], int n) {
    int max = *max_element(arr, arr+n);
    int min = *min_element(arr, arr+n);
    int range = max - min + 1;
 
    vector<int> count(range), output(n);
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
 
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }
 
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
 
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

8.4 复杂度分析

  • 时间复杂度:O(n+k),其中k是数组中数的范围
  • 空间复杂度:O(n+k)
  • 稳定性:稳定

9. 桶排序(Bucket Sort)

9.1 算法原理

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

9.2 Java实现

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
public void bucketSort(int[] arr, int bucketSize) {
    if (arr.length == 0) {
        return;
    }
     
    int minValue = arr[0];
    int maxValue = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }
 
    int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
    List<List<Integer>> buckets = new ArrayList<>(bucketCount);
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }
 
    for (int i = 0; i < arr.length; i++) {
        int bucketIndex = (int) Math.floor((arr[i] - minValue) / bucketSize);
        buckets.get(bucketIndex).add(arr[i]);
    }
 
    int currentIndex = 0;
    for (List<Integer> bucket : buckets) {
        Collections.sort(bucket);
        for (int i : bucket) {
            arr[currentIndex++] = i;
        }
    }
}

9.3 C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bucketSort(int arr[], int n) {
    int max_val = *max_element(arr, arr+n);
    int min_val = *min_element(arr, arr+n);
    int bucket_size = (max_val - min_val) / n + 1;
 
    vector<vector<int>> buckets(n);
 
    for (int i = 0; i < n; i++) {
        int bucket_index = (arr[i] - min_val) / bucket_size;
        buckets[bucket_index].push_back(arr[i]);
    }
 
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }
 
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

9.4 复杂度分析

  • 时间复杂度:O(n+k),其中k是桶的个数
  • 空间复杂度:O(n+k)
  • 稳定性:稳定

10. 基数排序(Radix Sort)

10.1 算法原理

基数排序是一种非比较型整数排序算法,其原理是将数据按位数切割成不同的数字,然后按每个位数分别比较。

10.2 Java实现

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
public void radixSort(int[] arr) {
    int max = getMax(arr);
 
    for (int exp = 1; max/exp > 0; exp *= 10) {
        countSort(arr, exp);
    }
}
 
int getMax(int[] arr) {
    int mx = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > mx)
            mx = arr[i];
    }
    return mx;
}
 
void countSort(int arr[], int exp) {
    int output[] = new int[arr.length]; 
    int i;
    int count[] = new int[10];
    Arrays.fill(count, 0);
 
    for (i = 0; i < arr.length; i++) {
        count[(arr[i] / exp) % 10]++;
    }
 
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
 
    for (i = arr.length - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
 
    for (i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

10.3 C++实现

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
int getMax(int arr[], int n) { 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) {
        if (arr[i] > mx) 
            mx = arr[i]; 
    }
    return mx; 
} 
  
void countSort(int arr[], int n, int exp) { 
    int output[n];
    int i, count[10] = {0}; 
  
    for (i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++; 
    }
  
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
  
    for (i = n - 1; i >= 0; i--) { 
        output[count[(arr[i] / exp) % 10] - 1] = arr[i]; 
        count[(arr[i] / exp) % 10]--; 
    } 
  
    for (i = 0; i < n; i++) {
        arr[i] = output[i]; 
    }
} 
  
void radixSort(int arr[], int n) { 
    int m = getMax(arr, n); 
  
    for (int exp = 1; m/exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

10.4 复杂度分析

  • 时间复杂度:O(d*(n+k)),d是最大数的位数
  • 空间复杂度:O(n+k)
  • 稳定性:稳定

总结

本文详细介绍了十种经典排序算法,包括它们的基本原理、Java与C++实现以及时间/空间复杂度分析和稳定性。虽然许多编程语言都提供了内置的排序函数,但了解这些底层排序算法的细节对于深入理解它们的工作原理、优化程序性能都是至关重要的。

通过本文,相信读者已经建立了对常用排序算法的全面认识。在具体的开发工作中,请根据待排序数据的规模、取值范围、稳定性要求等因素,权衡选择最适合的排序方法。

学无止境,让我们以娴熟掌握这些基础算法为起点,在算法与数据结构的世界中继续探索、继续精进!