Master common sorting algorithms in C++

C is a programming language widely used in computer programming, and the sorting algorithm is one of the commonly used algorithms in programming. Mastering sorting algorithms can improve your ability to write efficient programs and improve your programming skills. This article will introduce commonly used sorting algorithms in C.

1. Bubble sort

Bubble sort is a basic sorting algorithm that swaps larger elements into the sequence by comparing adjacent elements in sequence. end to achieve sorting. Specifically, bubble sort compares the sizes of adjacent elements in each round and swaps larger elements backward until the last element is sorted.

C code is as follows:

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;
            }
        }
    }
}

2. Selection sort

Selection sort is a simple sorting algorithm, which selects the unsorted part each time Sort by placing the smallest element at the end of the sorted section. Specifically, selection sort selects the smallest element in each round and exchanges it with the element at the current position.

C code is as follows:

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. Insertion sort

Insertion sort is a simple and intuitive sorting algorithm that inserts an element into an already in the sorted sequence, resulting in a longer sorted sequence. Specifically, each round of insertion sort inserts an element into the sorted subarray and moves the remaining elements backward.

C code is as follows:

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

4. Quick sort

Quick sort is an efficient sorting algorithm that selects a pivot element to sort the sequence Split into two parts, one smaller than the pivot element and one larger than the pivot element, and sort the two subsequences recursively. Specifically, quick sort selects a pivot element in each round, and places elements smaller than the pivot element to the left of the pivot element, and elements larger than the pivot element to the right. Then the left and right subsequences are sorted recursively in the same way.

C code is as follows:

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

5. Merge sort

Merge sort is a classic divide-and-conquer sorting algorithm, which divides the sequence into two subsequences, sort each subsequence separately, and finally merge the two ordered subsequences. Specifically, merge sort first splits the sequence into two subsequences, sorts the two subsequences recursively, and then merges the two ordered subsequences into one ordered sequence.

The C code is as follows:

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; // 左侧子数组的索引
    j = 0; // 右侧子数组的索引
    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);
    }
}

The above are the five sorting algorithms commonly used in C. Although algorithms may seem boring, they are an important part of programming. By learning sorting algorithms, we can improve the efficiency and quality of programming.

The above is the detailed content of Master common sorting algorithms in C++. For more information, please follow other related articles on the PHP Chinese website!