十大经典的排序算法

排序算法是《数据结构与算法》中最基本的算法之一，下面价绍了七种排序方式，分别是插入排序、希尔排序、选择排序、冒泡排序、归并排序等，附加源代码

1.冒泡排序

算法步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
//按升序排序
void bubblesort(int arr[],int len)
{
	int i, j;
	for (i = 0; i < len-1; i++)
	{
		for (j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

}
//冒泡排序降序排序
void bubblesort1(int arr[], int len)
{
	int i, j;
	for (i = 0; i < len - 1; i++)
	{
		for (j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}
int main()
{
	int arr[] = {1,5,3,2,9,15,6,4,59,65,32,31};
	int len = sizeof(arr) / sizeof(int);
	bubblesort1(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	puts("");
	system("pause");
	return 0;
}

2.选择排序

算法步骤：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

下面我写了两种，我觉得第一种比较直观易懂

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdio.h>
//交换两个数的值
void swap(int *num1,int *num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}
//选择排序升序01
void selectsort(int arr[],int len)
{
	int i, j;
	for (i = 0; i < len - 1; i++)
	{
		for (j = i + 1; j < len; j++)
		{
			if (arr[i] > arr[j])
			{
				swap(&arr[i], &arr[j]);
			}
		}
	}
}
//选择排序02
void selectsorT(int arr[], int len)
{
	int i, j;
	for (i = 0; i < len - 1; i++)
	{
		int min = i;//假设i为最小值
		for (j = i + 1; j < len; j++)
		{
			if (arr[i] > arr[j])//找到目前最小值
			{
				min = j;//记录最小值的位置
			}
		}
		swap(&arr[min], &arr[i]);//进行排序，将最小值与之前的假设的最小值i交换
	}
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	selectsorT(arr, len);
	for (int i = 0; i < len; i++)
			{
				printf("%d ", arr[i]);
			}
	system("pause");
	return 0;
}

3.插入排序

算法步骤：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
//插入排序,升序排序
void insertsort(int arr[],int len)
{
	int i, j, begin;
	for (i = 0; i < len; i++)
	{
		begin = arr[i];
		j = i - 1;
		while ((j >= 0) && (arr[j] > begin))
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = begin;
	}
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	insertsort(arr, len);
	for (int i = 0; i < len; i++)
			{
				printf("%d ", arr[i]);
			}
	system("pause");
	return 0;
}

4.希尔排序

算法步骤：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
//希尔排序升序排序
void shellsort(int arr[], int len) {
	int gap, i, j;
	int temp;
	for (gap = len >> 1; gap > 0; gap >>= 1)
	{
		for (i = gap; i < len; i++) 
		{
			temp = arr[i];
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
				arr[j + gap] = arr[j];
			arr[j + gap] = temp;
		}
	}
		
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	shellsort(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

5.归并排序

算法步骤：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
//归并排序
void mergesort(int arr[], int len) {
	int *a = arr;
	int *b = (int *)malloc(len * sizeof(int));
	int seg, start;
	for (seg = 1; seg < len; seg += seg) {
		for (start = 0; start < len; start += seg * 2) {
			int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			while (start1 < end1)
				b[k++] = a[start1++];
			while (start2 < end2)
				b[k++] = a[start2++];
		}
		int *temp = a;
		a = b;
		b = temp;
	}
	if (a != arr) {
		int i;
		for (i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	free(b);
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	mergesort(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

6.快速排序

算法步骤：

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
//快速排序
typedef struct _Range {
	int start, end;
} Range;

Range new_Range(int s, int e) {
	Range r;
	r.start = s;
	r.end = e;
	return r;
}

void swap(int *x, int *y) {
	int t = *x;
	*x = *y;
	*y = t;
}

void quicksort(int arr[],  int len) {
	if (len <= 0)
		return; 
	Range r[100];
	int p = 0;
	r[p++] = new_Range(0, len - 1);
	while (p) {
		Range range = r[--p];
		if (range.start >= range.end)
			continue;
		int mid = arr[(range.start + range.end) / 2]; 
		int left = range.start, right = range.end;
		do {
			while (arr[left] < mid) ++left;   
			while (arr[right] > mid) --right; 
			if (left <= right) {
				swap(&arr[left], &arr[right]);
				left++;
				right--;               
			}
		} while (left <= right);
		if (range.start < right) r[p++] = new_Range(range.start, right);
		if (range.end > left) r[p++] = new_Range(left, range.end);
	}
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	quicksort(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

7.堆排序

算法步骤：

  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。

C源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>
//堆排序
void swap(int *a, int *b) {
	int temp = *b;
	*b = *a;
	*a = temp;
}

void maxheapify(int arr[], int start, int end) {
	
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end)
	{
		if (son + 1 <= end && arr[son] < arr[son + 1]) 
			son++;
		if (arr[dad] > arr[son]) 
			return;
		else { 
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heapsort(int arr[], int len) {
	int i;
	
	for (i = len / 2 - 1; i >= 0; i--)
		maxheapify(arr, i, len - 1);
	
	for (i = len - 1; i > 0; i--) {
		swap(&arr[0], &arr[i]);
		maxheapify(arr, 0, i - 1);
	}
}
int main()
{
	int arr[] = { 1,5,3,2,9,15,6,4,59,65,32,31 };
	int len = sizeof(arr) / sizeof(int);
	heapsort(arr, len);
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
	system("pause");
	return 0;
}

我的github地址：https://github.com/zhajianliang/sort-algorithm.git

个人博客地址：https://zhajianliang.github.io

参考地址：https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

参考地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家