十大经典排序算法

引言

排序算法是计算机科学领域中最基础也最重要的算法之一，它们的作用不仅仅是对数据进行排序，还可以用于搜索、统计等各种领域。在本文中，我们将介绍十大经典排序算法，包括插入排序、选择排序、冒泡排序、快速排序、归并排序、堆排序、计数排序、桶排序、基数排序、鸡尾酒排序。

插入排序

插入排序算法的基本思想是将待排序数组分为已排序和未排序两个部分，首先将第一个元素视为已排序部分，然后遍历未排序部分的每一个元素，将它插入到已排序部分的适当位置。插入排序算法的时间复杂度为O(n^2)。

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i = 0 && arr[j] > key) 
        { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

选择排序

选择排序算法的基本思想是将待排序数组分为已排序和未排序两个部分，首先将未排序部分的第一个元素视为最小值，然后遍历未排序部分的每一个元素，找到最小值并将其放在已排序部分的末尾。选择排序算法的时间复杂度为O(n^2)。

void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 

    for (i = 0; i 

冒泡排序
冒泡排序算法的基本思想是将待排序数组分为已排序和未排序两个部分，从未排序部分的第一个元素开始，两两比较相邻的元素，如果顺序不对就交换它们的位置，直到所有未排序部分的元素都被遍历完毕。冒泡排序算法的时间复杂度为O(n^2)。
void bubbleSort(int arr[], int n) 
{ 
    int i, j; 
    for (i = 0; i  arr[j+1]) 
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    } 
}


快速排序
快速排序算法的基本思想是选择一个基准元素，将待排序数组分为小于基准元素和大于基准元素的两个子数组，然后递归地对子数组进行排序，最终将它们合并成一个有序数组。快速排序算法的时间复杂度为O(nlogn)。
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];
    int i = (low - 1); 

    for (int j = low; j  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;