几种常见排序算法的实现

一、冒泡排序

1.百度百科

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2.C语言实现

分别定义两个函数(从小到大排序)

//冒泡(一轮冒泡之后，数组的最后一个为最大值)
void Bubble(int arr[], int n){
    
    for(int i = 0; i < n-1; i++){
    
        int temp;
        if(arr[i] > arr[i+1]){
    
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//冒泡排序
void bubbleSorrt(int arr[], int n){
    
    for(int i = n; i > 0; i--){
    
        Bubble(arr, i);
    }

for循环嵌套实现

//冒泡排序
void bubbleSorrt(int arr[], int n){
    
    for(int i = 0; i < n-1; i++)//控制冒泡的轮数
    {
    
        for(int j = 0; j < n-1-i; j++)//控制每一轮冒泡数组元素交换的次数
        {
    
            int temp;
            if(arr[j] > arr[j+1]){
    
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

示例

#include <stdio.h>

//冒泡(一轮冒泡之后，数组的最后一个为最大值)
void Bubble(int arr[], int n){
    
    for(int i = 0; i < n-1; i++){
    
        int temp;
        if(arr[i] > arr[i+1]){
    
            temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
        }
    }
}
//冒泡排序
void bubbleSorrt(int arr[], int n){
    
    // for(int i = n; i > 0; i--){
    
    //     Bubble(arr, i);
    // }
    for(int i = 0; i < n-1; i++)//控制冒泡的轮数
    {
    
        for(int j = 0; j < n-1-i; j++)//控制每一轮一轮冒泡的次数，每一轮减一次
        {
    
            int temp;
            if(arr[j] > arr[j+1]){
    
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main(){
    
    int arr[7] = {
    6, 7, 5, 8, 4, 2, 9};
    bubbleSorrt(arr, 7);
    for(int i = 0; i < 7; i++){
    
        printf("%d ", arr[i]);
    }
    printf("\n");
}

二、选择排序

1.百度百科

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

2.图解

红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

3.C语言实现

定义两个函数

//找到最大值的位置(从小到大排序)
int findMaxPos(int arr[], int n){
    
    int Max_pos = 0;
    int max = arr[Max_pos];
    for(int i = 0; i < n; i++){
    
        if(arr[i] > max){
    
            max = arr[i];
            Max_pos = i;
        }
    }
    return Max_pos;
}
//找到最小值的位置(从大到小排序)
int findMinPos(int arr[], int n){
    
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
    
        if(arr[i] < min){
    
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//选择排序
void selectionSort(int arr[], int n){
    
    for(int i = n; i > 0; i--){
    
        int pos = findMinPos(arr, i);//i表示这个数组的大小
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//将最大值与末项交换位置
    }
}

示例

#include <stdio.h>

//找到最小值的位置(从大到小排序)
int findMinPos(int arr[], int n){
    
    int Min_pos = 0;
    int min = arr[Min_pos];
    for(int i = 0; i < n; i++){
    
        if(arr[i] < min){
    
            min = arr[i];
            Min_pos = i;
        }
    }
    return Min_pos;
}

//选择排序
void selectionSort(int arr[], int n){
    
    for(int i = n; i > 0; i--){
    
        int pos = findMinPos(arr, i);//改变排列顺序只需改变函数名
        int temp = arr[pos];
        arr[pos] = arr[i-1];
        arr[i-1] = temp;//将最大(小)值与末项交换位置
    }
}

int main(){
    
    int arr[8] = {
    6, 7, 10, 11, 4, 11, 9, 7};
    selectionSort(arr, 8);
    for(int i = 0; i < 8; i++){
    
        printf("%d ", arr[i]);
    }
    printf("\n");
}

三、插入排序

1.维基百科

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2.图解

3.代码实现

//插入排序
void insertionSort(int arr[], int len){
    
    for(int i = 1; i < len; i++){
    
        int pos = i;//pos表示要插入的元素的位置
        int key = arr[pos];//key表示要插入的元素,整个插入过程不会更改
        while(arr[pos-1] > key && pos > 0){
    
            arr[pos] = arr[pos-1];
            pos--;//位置向前移动一位继续比较
        }
        arr[pos] = key;//将要插入的元素继续保存在pos位置上
    }
}

示例

#include <stdio.h>

//插入排序
void insertionSort(int arr[], int len){
    
    for(int i = 1; i < len; i++){
    
        int pos = i;//pos表示要插入的元素的位置
        int key = arr[pos];//key表示要插入的元素
        while(arr[pos-1] > key && pos > 0){
    
            arr[pos] = arr[pos-1];
            pos--;//位置向前移动一位继续比较
        }
        arr[pos] = key;//将要插入的元素继续保存在pos位置上
    }
}

int main(){
    
    int arr[12] = {
    6, 7, 10, 11, 4, 11, 9, 7, 3, 1, 8, 0};
    insertionSort(arr, 12);
    for(int i = 0; i < 12; i++){
    
        printf("%d ", arr[i]);
    }
    printf("\n");
}