冒泡排序，选择排序，直接插入排序，二分查找排序

2019-11-06 07:24:39

字体：大中小

来源：转载

供稿：网友

今天继续对排序做个整理吧三个简单排序—冒泡，选择，直接插入

首先是冒泡排序(Bubble Sort )：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

这里写图片描述

时间复杂度 O(n^2) 最优时间复杂度 O(n) 平均时间复杂度 O(n^2)

C语言实现：

//冒泡排序初级版void BubbleSort0(int *arr, int len){ int i; int j; for(i = 0; i < len; i++) { for(j = i + 1; j < len; j++) { if(arr[i] > arr[j]) { Swap(arr,i, j); } } }}//正宗冒泡排序void BubbleSort(int *arr, int len){ int i; int j; for(i = 0; i < len; i++) { for(j = len -1; j >= i; j--) //j从后往前，将小的值交换到i的位置 { if(arr[i] > arr[j]) { Swap(arr, i, j); } } } }//优化冒泡排序_对于已经有序的序列不再进行循环void BubbleSort1(int *arr, int len){ int i; int j; bool flag = true; //增加一个flag作为标记 for(i = 0; i < len && flag; i++) //若flag = true 则退出循环 { flag = false; //初始化为false for(j = len -1; j >= i; j--) { if(arr[i] > arr[j]) { Swap(arr, i, j); flag = true; //如果有数据交换,则flag = ture } } } }

选择排序(Selection sort)：

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

这里写图片描述

时间复杂度 О(n²) 最优时间复杂度 О(n²) 平均时间复杂度 О(n²)

C语言实现如下：

void SelectSort(int *arr, int len){ int i; int j; int min; for(i = 0; i < len; i++) { min = i; //将当前下标作为最小值下标 for(j = i + 1; j < len; j++) { if(arr[i] > arr[j]) { min = j; //找到最小值，将最小值下标给min if(i != min) { Swap(arr, i, min); } } } }}

直接插入排序(Insertion Sort)：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

这里写图片描述

时间复杂度 O(n^2) 最优时间复杂度 O(n) 平均时间复杂度 O(n^{2})

C语言实现如下：

void InsertSort(int *arr, int len){ int i; int j; int tmp; for (i = 1; i < len; i++) { tmp = arr[i]; j = i - 1; for (; j >= 0 && arr[j] > tmp; j--) arr[j + 1] = arr[j];//最后一次执行该语句后，跳出当前for循环前，会再一次执行j-- arr[j + 1] = tmp;//执行完上一个语句（即for语句）后，跳出的位置保存在j中，此时arr[j]的值是没有经过移动的，不能替换，应该替换的是arr[j+1] }}

二分插入排序(BinarySort)：

是插入排序的一种变形，由于用到了二分查找算法，所以叫做二分插入排序，这样关键字的比较次数就会减少，数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以二分插入排序的时间复杂度是O(n^2)。int Binary_Search(int *arr, int len, int key){ int low = 0; int high = len; while (low <= high ) { int mid = (low + high ) / 2; if (arr[mid] > key) { high = mid - 1; } else low = mid + 1; } return low; }//将数组分为俩个区域 //有序区 0 -- （i-1） --> 初始有一个元素//无序区 i -- (len-1)void BinarySort(int *arr, int len){ for (int i = 1; i < len; i++) { int tmp = arr[i]; int index = Binary_Search(arr, i - 1, tmp); for (int j = i; j > index; j--) { arr[j] = arr[j - 1]; } arr[index] = tmp; }}

参考：

二分法插入排序_百度百科折半插入排序–俩种java实现方法二分搜索算法-维基百科

上一篇：策略模式多种方式实现字符串比较

下一篇：使用子类型化优化标签类