常见排序算法总结

展现的代码默认为升序排序.

冒泡排序

思想:比较相邻的元素，然后如果左边大于右边则交换位置.越大的数会越靠右，每次排序产生一个最大的数，并在第二个循环中取消对该位置的遍历.

时间复杂度：O(N²) (两个嵌套循环)

空间复杂度：O(1)

Code

Language:C

void BubbleSort(int *arr, int size)  
{  
    int i, j, tmp;  
    for (i = 0; i < size - 1; i++) {  
        for (j = 0; j < size - i - 1; j++) {  
            if (arr[j] > arr[j+1]) {  
                tmp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = tmp;  
            }  
        }  
    }  
}

升序排列:a[k] > a[k+1]

降序排列:a[k] < a[k+1]

选择排序

思想:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

时间复杂度：O(N²) (两个嵌套循环)

空间复杂度：O(1)

Code

Language:C

void SelectionSort(int *arr, int size)
{
    int i, j, k, tmp;
    for (i = 0; i < size - 1; i++) {
        k = i;
        for (j = i + 1; j < size; j++) {
            if (arr[j] < arr[k]) {//如果当前遍历到的元素小于或大于之前的假定的极小值（极大值），则更新索引
                k = j;
            }
        }
        tmp = arr[k];//将极值元素和边元素进行交换
        arr[k] = arr[i];
        arr[i] = tmp;
    }
}

升序排列:arr[j] < arr[k]

降序排列:arr[j] > arr[k]

插入排序

思想:构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度：O(N²) (两个嵌套循环)

空间复杂度：O(1)

Code

Language:C

void InsertionSort(int *arr, int size)    
{    
    int i, j, tmp;    
    for (i = 1; i < size; i++) {//从第二个元素开始遍历，默认为有序序列；遍历n次则数组从arr[0]到arr[n]构成有序数列；完全排序时间为遍历n-1次    
        if (arr[i] < arr[i-1]) {//如果后者比前者小，则认为构成逆序；在前序有序序列中查找后者的位置，并插入元素    
            tmp = arr[i];//待插入数组元素    
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {//找到第一个比tmp大的元素，将该元素及其之后的元素全部后移一位
                arr[j+1] = arr[j];    
            }  
            arr[j+1] = tmp;//插入元素    
        }          
    }    
}

升序排列:arr[i] < arr[i-1]

降序排列:arr[i] > arr[i-1]

归并排序

思想:归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

时间复杂度：O(nlog2n)

空间复杂度：O(n)

Code

Language:C

#define MAXSIZE 100  
 
void Merge(int *SR, int *TR, int i, int middle, int rightend) //子序列合并
{
    int j, k, l;  
    for (k = i, j = middle + 1; i <= middle && j <= rightend; k++) {//遍历SR数组的前半部分和后半部分（均为有序子序列），将数据按从小到大排序
        if (SR[i] < SR[j]) {
            TR[k] = SR[i++];
        } else { 
            TR[k] = SR[j++];
        }  
    }  
    if (i <= middle) {//如果前半部分有剩余
        for (l = 0; l <= middle - i; l++) {
            TR[k + l] = SR[i + l];
        }  
    }  
    if (j <= rightend) {//如果后半部分有剩余
        for (l = 0; l <= rightend - j; l++) {
            TR[k + l] = SR[j + l];  
        }
    }  
}  
  
void MergeSort(int *SR, int *TR1, int s, int t) 
{  
    int middle;  
    int TR2[MAXSIZE + 1];  
    if (s == t) {//如果排序的对象长度为1，则返回它本身
        TR1[s] = SR[s]; 
    } else {  
        middle = (s + t) / 2;
        MergeSort(SR, TR2, s, middle);
        MergeSort(SR, TR2, middle + 1, t);
        Merge(TR2, TR1, s, middle, t);//将序列分割为两个子序列
    }  
}

升序排列:SR[i] < SR[j]

降序排列:SR[i] > SR[j]

快速排序

思想:通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

时间复杂度：O(nlog2n)

空间复杂度：O(nlog2n)

思路解释：

假设我们有一个待排序的数组：[5, 3, 8, 2, 7, 1, 4]。

我们选择数组的第一个元素 5 作为基准值（pivot）。
接下来，我们将数组分成两部分，一部分是小于基准值的元素，另一部分是大于基准值的元素。这个过程称为划分（partitioning）。
当前数组状态：[5, 3, 8, 2, 7, 1, 4]
划分后的状态：[3, 2, 1, 4] | 5 | [8, 7]
然后，我们对划分后的两个子数组 [3, 2, 1, 4] 和 [8, 7] 分别进行递归排序。
对左侧子数组 [3, 2, 1, 4] 进行快速排序：
- 选取基准值 3。
- 划分后的状态：[2, 1] | 3 | [4]
对右侧子数组 [8, 7] 进行快速排序：
- 选取基准值 8。
- 划分后的状态：[7] | 8 | []
继续对子数组进行递归排序，直到每个子数组只有一个元素。
最终排序结果为：[1, 2, 3, 4, 5, 7, 8]

Code

Language:C

void QuickSort(int *arr, int maxlen, int begin, int end)  
{  
    int i, j;  
    if (begin < end) {  
        i = begin + 1;  
        j = end;        
        while (i < j) {  //将arr[begin]设为基准值，比它小的在它左侧，大的在右侧，划分数据
            if(arr[i] > arr[begin]) {  
                swap(&arr[i], &arr[j]); 
                j--;  
            } else {  
                i++; 
            }  
        }  
        if (arr[i] >= arr[begin]) {  
            i--;  
        }  
        swap(&arr[begin], &arr[i]);      
        QuickSort(arr, maxlen, begin, i);  
        QuickSort(arr, maxlen, j, end);  
    }  
}  
 
void swap(int *a, int *b)//实现交换数据    
{  
    int temp;  
    temp = *a;  
    *a = *b;  
    *b = temp;  
}

升序排列:arr[i] > arr[begin]

降序排列:arr[i] < arr[begin]

计数排序

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

时间复杂度：O(n+k)

空间复杂度：O(n+k)

Code

Language:C

升序：

void CountingSort(int *A, int *B, int n, int k)  
{  
    int *C = (int *)malloc(sizeof(int) * (k + 1));  
    int i;  
    for (i = 0; i <= k; i++) {  
        C[i] = 0;  
    }  
    for (i = 0; i < n; i++) {  
        C[A[i]]++;  
    }  
    for (i = 1; i <= k; i++) {  
        C[i] = C[i] + C[i - 1];  
    }  
    for (i = n - 1; i >= 0; i--) {  
        B[C[A[i]] - 1] = A[i];  
        C[A[i]]--;  
    }  
}

降序：

void CountingSort(int *A, int *B, int n, int k)  
{  
    int *C = (int *)malloc(sizeof(int) * (k + 1));  
    int i;  
    for (i = 0; i <= k; i++) {  
        C[i] = 0;  
    }  
    for (i = 0; i < n; i++) {  
        C[A[i]]++;  
    }  
    for (i = k - 1; i >= 0; i--) {  
        C[i] += C[i + 1];
    }  

    for (i = 0; i < n; i++) {  
        B[C[A[i]] - 1] = A[i];
        C[A[i]]--;  
    }  
}

常见排序算法总结 ​

冒泡排序 ​

选择排序 ​

插入排序 ​

归并排序 ​

快速排序 ​

计数排序 ​

常见排序算法总结

冒泡排序

选择排序

插入排序

归并排序

快速排序

计数排序