首页 > 代码库 > 1，排序算法
1，排序算法
不管是C++还是JAVA，都有相应的库提供排序函数。比如，c++中<algorithm>提供了sort函数。不过，能了解常见排序算法的原理，在面试或工作中都有一定的帮助。下面，对常见排序算法进行梳理。
常见的排序算法有：插入排序，选择排序，冒泡排序，希尔排序，快速排序，归并排序，基数排序，堆排序。
一、插入排序
1，思想：提到插入排序，一个朋友给我举了一个非常传神的栗子，简单形象，通俗易懂。大家都有打扑克牌吧，一般来说，我们抓牌后都是按顺序放在手中。每当我们新抓一张牌，就把这张牌插入到排好序的手牌中。而这正符合插入排序的思想，在有序的序列中插入新的元素。
7 6 1 5 3, 开始时，我们有一张手牌7，它自己是有序的(一个元素)，然后我们抓起来一张6，比7小，两者交换。
6 7 1 5 3，然后来了一张1，拿它和有序序列6,7比较，插入到起始位置
1 6 7 5 3，然后来了一张5，拿它和有序序列1,6,7比较，插入
1 5 6 7 3，最后来了一张3，拿它和有序序列1,5,6,7比较，插入
1 3 5 6 7，得到排序结果
show me the code.我们先看看C++的实现代码。
for (int i=1; i<v.size(); i++){ int key = v[i]; int j = i-1; while (j >= 0 && v[j] > key){ v[j+1] = v[j]; j--; } v[j+1] = key;}然后，我们再看看python实现。
def insert_sort(lists): count = len(lists) for i in range(1,count) key = lists[i] j = i - 1 while j >= 0: if lists[i] > key: lists[j + 1] = lists[j] lists[j] = key j -= 1 return lists值得注意的是，c++实现和python实现在交换数据这个细节上不同。C++, 如果排序序列中的值比key小且j>=0，我依次把排序序列往右移，直到不满足时，我们把key赋给那个位置。而python中，满足条件时，交换相邻两个元素。
实现细节不同，但两者思想一致。
2，时间复杂度
外层循环为待排序序列个数n，内循环中，如果考虑完全你虚的情况，则需交换数据（移动数据）n次，所以时间复杂度为O(N^2).
二、选择排序
选择排序的思想简单粗暴。从序列中找到最小值，放到第一个位置，然后在剩余元素中找最小值放在第二位置.....bulabula.......。有一种很通俗的说法，喧杂排序是固定位置找元素，而插入排序是固定元素找位置。很形象。
for(int i=0; i<v.size(); i++){ int min = v[i]; int temp; int index = i; for(int j = i + 1; j < v.size(); j++){ if(v[j] < min){ min = v[j]; index = j; } } temp = v[i]; v[i] = min; v[index]= temp;}同样，我们看看python实现。
def select_sort(lists): count = len(lists) for i in range(0, count): min = i for j in range(i + 1, count): if lists[min] < lists[j]: min =j lists[min], lists[i] = lists[i], lists[min] return lists
三、冒泡排序
1，思想。冒泡排序，人如其名，如果考虑升序的话，就是比较相邻元素大小，将小的元素左移，大的元素右移，经过一轮移动，可以将最小元素移到最左边，或者最大元素移到最右边。就像气泡一样上浮（小元素左移），或者石头落入水底（大元素右移）。两种移动方法，可凭自己喜欢选择。
时间复杂度O(N^2).
C++代码，小元素左移。
for (int i=0; i<v.size(); i++){ int temp = 0; for(int j=v.size()-1; j > i; j--){ if (v[j] < v[j-1]){ temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } }
}python代码，大元素右移。
def bubble_sort(lists): count = len(lists) for i in range(0, count): for j in range(j+1, count): if lists[i] > lists[j]: lists[i], lists[j] = lists[j], lists[i] return lists2，冒泡排序的优化
若在某一轮排序中未发现气泡位置的交换，则说明待排序的无序序列其实已经“有序”了。因此，冒泡排序可在此轮排序后终止。为此，我们增加一个标志位flag，在每轮排序前，先将其置为false，若排序过程中发生了交换，则将其置为true。各轮排序结束时检查flag，若未曾发生过交换则终止算法。
bool flag; for (int i = 0; i < len-1; i++) { int temp = 0; flag = false; for (int j = len-1; j > i; j--) { if (ar[j] < ar[j - 1]){ temp = ar[j]; ar[j] = ar[j - 1]; ar[j - 1] = temp; flag = true; } } if (!flag) { break; } }另一种写法
void NewBubbleSort(int a[], int n){ int exchange; int temp; int j=0; exchange = n-1; while( exchange ){ exchange = 0; for( j = 0 ;j < n-1;j++ ){ if(a[j] > a[j+1] ){ temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; exchange = j; } } }}占时写到这吧，脖子好酸啊.......
1，排序算法