经典排序算法一（冒泡排序、快速排序）经典排序算法一（冒泡排序、

一张经典算法图镇楼。

文章图片
十大经典排序算法正文常用术语说明
稳定：如果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); }