几种常见排序算法的实现

一、冒泡排序

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