冒泡排序
基本思想：
两个数比较大小，较大的数下沉，较小的数冒起来。
比较过程：
1、比较相邻的两个数据，如果第二个数小，就交换位置。
2、从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
3、继续重复上述过程，依次所有数排好位置。
完整代码：
void bubble_sort(int arr[], int length){
for (int i = 0; i < length;i++) {
for (int j = 0; j <length – i – 1; j++) {
if (arr[j] > arr[j +1]) {
swap(arr[j], arr[j+ 1]);
}
}
}
}
选择排序
基本思想：
1、在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
2、第二次遍历n-2个数，找到最小的数值与第二个元素交换；
……
3、第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
完整代码：
void select_sort(int arr[], int length){
for (int i = 0; i < length;i++) {
int min = i;
for (int j = i + 1; j <length; j++) {
if (arr[min] >arr[j]) {
min = j;
}
}
if (min != i) {
swap(arr[min], arr[i]);
}
}
}
插入排序
基本思想：
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
完整代码：
void insert_sort(int arr[], int length){
for (int i = 1; i < length;i++) {
int key = arr[i];
int j = i – 1;
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = key;
}
}
快速排序
1、先从数列中取出一个数作为key值；
2、将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
3、对左右两个小数列重复第二步，直至各区间只有1个数。
完整代码：
void quick_sort(int arr[],int left,intright){
if(left>= right) return;
inti = left;
intj = right;
intkey = arr[left];
while(i< j){
while(i < j && key <=arr[j]) j–;
arr[i] = arr[j];
while(i < j && key >=arr[i]) i++;
arr[j] = arr[i];
}
arr[i]= key;
quick_sort(left,i-1);
quick_sort(i+1,right);
}
归并排序
完整代码：
void merge(int arr[],int r[],int left,int right){
//先分解
if(left == right) return;
int mid = (left+right)/2;
merge(left,mid);
merge(mid+1,right);
//后合并
int i = left, j = mid+1;
int k = left;
while(i <= mid &&j<= right){
if(arr[i]<=arr[j]) r[k++]= arr[i++];
else r[k++] =arr[j++];
}
while(i<=mid) r[k++]=arr[i++];
while(j<=right)r[k++]=arr[j++];
for(i=left;i<=right;i++)arr[i] =r[i];
}
|
排序法 |
平均时间 |
最差情形 |
稳定性 |
额外空间 |
备注 |
|
冒泡 |
O(n2) |
O(n2) |
稳定 |
O(1) |
n小时较好 |
|
选择 |
O(n2) |
O(n2) |
不稳定 |
O(1) |
n小时较好 |
|
插入 |
O(n2) |
O(n2) |
稳定 |
O(1) |
大部分已排序时较好 |
|
基数 |
O(logRB) |
O(logRB) |
稳定 |
O(n) |
B是真数(0-9)， R是基数(个十百) |
|
Shell |
O(nlogn) |
O(ns) 1<s<2 |
不稳定 |
O(1) |
s是所选分组 |
|
快速 |
O(nlogn) |
O(n2) |
不稳定 |
O(nlogn) |
n大时较好 |
|
归并 |
O(nlogn) |
O(nlogn) |
稳定 |
O(1) |
n大时较好 |
|
堆 |
O(nlogn) |
O(nlogn) |
不稳定 |
O(1) |
n大时较好 |
转自公众号：
信息学少儿编程