c++数组排序的5种方法实例代码

C++ 数组排序的 5 种方法实例代码

本篇文章介绍了使用 C++ 实现数组排序的 5 种方法，包括冒泡排序、选择排序、插入排序、希尔排序和快速排序。下面我们就分别详细阐述各种排序方法的实现。

冒泡排序

冒泡排序的基本思想是比较相邻的两个元素，如果顺序错误就交换位置。我们重复地执行这个过程，直到排序完成。示例代码如下：

void BubbleSort(int array[], int length) {
    for(int i = 0; i < length - 1; i++) {
        for(int j = 0; j < length - i - 1; j++) {
            if(array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

选择排序

选择排序的基本思想是在未排定的部分中找到最小元素，然后将其放到已排定部分的末尾。选择排序需要不断地找到未排定部分的最小元素，但是与冒泡排序不同的是，选择排序只会在遍历完整个未排定部分之后，才会将最小元素与未排定部分的首位交换。示例代码如下：

void SelectionSort(int array[], int length) {
    for(int i = 0; i < length - 1; i++) {
        int min_index = i;
        for(int j = i + 1; j < length; j++) {
            if(array[j] < array[min_index]) {
                min_index = j;
            }
        }
        int temp = array[i];
        array[i] = array[min_index];
        array[min_index] = temp;
    }
}

插入排序

插入排序的基本思想是将未排定的元素逐个插入到已排定的部分中。要将元素插入到已排定部分中，我们需要从后往前比较已排定部分的元素，直到找到插入位置，然后将插入位置之后的元素往后移。示例代码如下：

void InsertionSort(int array[], int length) {
    for(int i = 1; i < length; i++) {
        int current = array[i];
        int j = i - 1;
        while(j >= 0 && array[j] > current) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = current;
    }
}

希尔排序

希尔排序的基本思想是将数组分成若干个子序列，分别对每个子序列进行插入排序，然后依次逐步缩小子序列的范围，直到最后整个序列变为有序。示例代码如下：

void ShellSort(int array[], int length) {
    // 选取一个合适的增量
    for(int gap = length / 2; gap > 0; gap /= 2) {
        // 对子序列分别进行插入排序
        for(int i = gap; i < length; i++) {
            int temp = array[i];
            int j = i;
            while(j >= gap && array[j - gap] > temp) {
                array[j] = array[j - gap];
                j -= gap;
            }
            array[j] = temp;
        }
    }
}

快速排序

快速排序的基本思想是选择一个基准元素，将数组分成两个部分，小于基准元素的元素和大于基准元素的元素，然后对这两个部分分别进行快速排序。示例代码如下：

void QuickSort(int array[], int left, int right) {
    if(left < right) {
        int pivot = array[left];
        int i = left;
        int j = right;
        while(i < j) {
            while(i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while(i < j && array[i] <= pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        QuickSort(array, left, i - 1);
        QuickSort(array, i + 1, right);
    }
}

以上就是使用 C++ 实现数组排序的 5 种方法的详细实现过程。