Fork me on GitHub

各种排序算法

最近准备弄一些简单的算法,先从排序开始吧,也不知道可以坚持多久,先这样。

冒泡排序

冒泡排序维基百科介绍

冒泡排序(英语:Bubble Sort,台灣另外一種譯名為:泡沫排序)是一種簡單的排序算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

C语言实现

原始版本

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort(int *a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

一点优化的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(int *a, int n) {
int flag = 0;
for (int i = 0; i < n - 1; i++) {
flag = 0;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
flag = 1;
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
if (flag == 0) {
break;
}
}
}

扩展

交换2个变量的一些方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int c1 = 1;
int c2 = 100;

// 局部变量
int temp = c1;
c1 = c2;
c2 = temp;

// 加减法 && 乘除法
c1 = c1 + c2; // c1 = c1 * c2;
c2 = c1 - c2; // c2 = c1 / c2;
c1 = c1 - c2; // c1 = c1 - c2;

// 异或
c1 = c1 ^ c2;
c2 = c1 ^ c2;
c1 = c1 ^ c2;
获取数组中的最大值最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
void getMaxMin(int *a, int n, int *max, int *min) {
int tempMax = a[0];
int tempMin = a[0];
for (int i = 1; i < n; i++) {
if (a[i] > tempMax) {
tempMax = a[i];
} else if (a[i] < tempMin) {
tempMin = a[i];
}
}
*min = tempMin;
*max = tempMax;
}

选择排序

选择排序维基百科介绍

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(int *a, int n) {
int min, temp;
for (int i = 0; i < n; i++) {
min = i;
for (int j = i; j < n; j++) {
if (a[min] > a[j] ) {
min = j;
}
}
if (min != i) {
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}

插入排序

插入排序维基百科介绍

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertSort(int *a, int n) {

for (int i = 1; i < n; i++) {
// 从1 开始取出后面的元素来来插入之前排好的数组中

// 取出 i 位置上的数
int temp = a[i];

// 遍历排序好的数组
for (int j = i; j >= 0; j--) {
// 如果取出来的大于a[j-1] 说明已经排序好了
if (a[j-1] < temp) {
// 赋值退出此层循环
a[j] = temp;
break;
} else {
// 排序好的数组 a[j] = a[j-1];
a[j] = a[j-1];
}
}
}
}

希尔排序 ShellSort

归并排序 MergeSort

快速排序 QuickSort

堆排序 HeapSort

- END -
扫一扫上面的二维码图案,加我微信

文章作者:梁大红

特别声明:若无特殊声明均为原创,转载请注明,侵权请联系

版权声明:署名-非商业性使用-禁止演绎 4.0 国际