笔记大全

数据结构排序算法总结

更新时间：2023-12-02

前言

排序算法是计算机科学中的重要概念之一，它用于将一组元素按照特定的顺序重新排列。在实际的软件开发过程中，我们经常需要对数据进行排序，以便更方便地进行搜索、查找或优化算法的执行效率。本文将介绍一些常用的数据结构排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。

冒泡排序

冒泡排序是一种简单直观的排序算法，它通过多次交换相邻元素的位置，将最大或最小的元素逐渐“冒泡”到数组的一端。具体实现如下：

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]) {
                // 交换arr[j]和arr[j+1]
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

选择排序

选择排序是一种简单但低效的排序算法，它通过重复从未排序的部分选择最小元素，并将其放置到已排序部分的末尾。具体实现如下：

def selectionSort(arr):
    n=len(arr)
    for i in range(n):
        min_idx=i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx=j
        arr[i], arr[min_idx]=arr[min_idx], arr[i]

插入排序

插入排序是一种简单且稳定的排序算法，它通过构建有序序列，对于未排序部分的每个元素，在有序序列中寻找合适的位置插入。具体实现如下：

function insertionSort(arr) {
    let n=arr.length;
    for (let i=1; i < n; i++) {
        let key=arr[i];
        let j=i - 1;
        while (j >=0 && arr[j] > key) {
            arr[j + 1]=arr[j];
            j--;
        }
        arr[j + 1]=key;
    }
}

快速排序

快速排序是一种常用的基于比较的排序算法，它通过选择一个基准元素将数组分为两个子数组，然后递归地对子数组进行排序。具体实现如下：

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

归并排序

归并排序是一种高效的排序算法，它通过将两个已排序的子序列合并成一个序列，不断地递归地对子序列进行排序，最后得到完全有序的序列。具体实现如下：

def mergeSort(arr):
    if len(arr) > 1:
        mid=len(arr) // 2
        L=arr[:mid]
        R=arr[mid:]
        
        mergeSort(L)
        mergeSort(R)
 
        i=j=k=0
 
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k]=L[i]
                i +=1
            else:
                arr[k]=R[j]
                j +=1
            k +=1
 
        while i < len(L):
            arr[k]=L[i]
            i +=1
            k +=1
 
        while j < len(R):
            arr[k]=R[j]
            j +=1
            k +=1

堆排序

堆排序是一种高效的排序算法，它利用堆的特性来对数组进行排序，堆排序包括建堆和排序两个过程。具体实现如下：

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; // 节点 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);
    }
}

总结

在本文中，我们介绍了常用的六种数据结构排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。每种排序算法都有其独特的特点和适用场景，程序员需要根据具体的应用场景和数据规模选择合适的排序算法。了解不同排序算法的原理和实现细节可以帮助我们编写高效、稳定且可靠的程序。

c语言编程笔录