一张经典算法图镇楼。
十大经典排序算法
正文
常用术语说明
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。
排序分类
对于我这种只是想简单了解一下排序算法的人来说，这6种（冒泡排序、快速排序、简单选择排序、直接插入排序、堆排序和希尔排序）算法的学习就已经足够了。
算法介绍（全部以C语言的形式介绍）
int array[] = {6 ,1 ,2 ,7 ,9 ,3 ,4 ,5 ,10 ,8};
int num = sizeof(array)/sizeof(int);
- 冒泡排序（Bubble Sort）
人生中接触的第一种排序方法。
- 算法描述
通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。
- 算法实现
for (int i = 0; i < num - 1; i++) {
for (int j = 0; j < num - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
- 快速排序（Quick Sort）
-
算法描述
1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素； 2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边； 3.对左右两个分区重复以上步骤直到所有元素都是有序的。 所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。
- 算法实现
void sort(int *a,int left,int right) {
if (left >= right) {
return;
}
// 由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
// 从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
int i = left;
int j = right;
int key = a[i]; //a[i]就是第一个坑
while (i < j) {
// 从右向左找小于x的数来填s[i]
while (i < j && key <= a[j]) {
j--;
}
a[i] = a[j];
while (i < j && key >= a[i]) {
i++;
}
a[j] = a[i];
}
a[i] = key;
sort(a, left, i-1);
sort(a, i+1, right);
}
还有一种比较个性理解的版本:一次循环先交换大小的，最后才和基数的交换。
在博客坐在马桶上看算法：快速排序看到的，评论区各种吵架，说这不是快排。感觉思路是一样的。代码如下
void sort1(int *a,int left,int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int key = a[i];
while (i != j) {
//顺序很重要，要先从右边开始找
while (i < j && key <= a[j]) {
j--;
}
//再找左边的
while (i < j && key >= a[i]) {
i++;
}
//交换两个数在数组中的位置
if(i < j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=key;
sort1(a, left, i-1);
sort1(a, i+1, right);
}
