1. 首页
  2. 文章中心
  3. 数据结构及其算法

各种排序算法的实现

112 阅读 0 评论
我是靠谱客的博主 生动世界，这篇文章主要介绍各种排序算法的实现，现在分享给大家，希望可以做个参考。

 

插入排序

基本思想：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好的序的一组元素的合适的位置上去，直到元素全部插完为止。

1.直接插入排序

基本思想： 
当插入第i个元素时，前面的array[0]、array[1]、array[2]……array[i-1]已经排好序，此时用array[i]的排序码与array[i-1]、array[i-2]……的排序码进行比较，找到插入位置将array[i]插入，原来位置上的元素顺序右移。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入排序-直接排序
void InsertSort(int *a, int n)
{
	assert(a != NULL);
	int i = 0;
	for (; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0 && a[end]>tmp)
		{
			a[end + 1] = a[end];
			--end;
		}
		a[end + 1] = tmp;
	void PrintArray(int * a, int n)}
}

2. 二分插入排序

优点：查找更快，减少比较操作的次数，效率更高。

复制代码
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
//二分插入排序
void InsertSort_OP(int *a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		//在已序序列中查找待插入元素的位置
		int left = 0;
		int right = i;
		int key = a[i];
		while (left <= right)
		{
			int mid = left + ((right - left) >> 1);
			if (key < a[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
		//搬移元素
		int end = i - 1;
		while (end >= left)
		{
			a[end + 1] = a[end];
			end--;
		}

		//插入元素
		a[left] = key;
	}
}

3.希尔排序

基本思想： 
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。 
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ShellSort(int *a, int n)
{
	assert(a != NULL);
	int gap = n;
	int i = 0;
	if (gap > 1)
	{
		gap = gap / 3 + 1;
	}
	for (; i < gap; ++i)
	{
		int end = i;
		int tmp = a[end + gap];
		while (end >= 0 && a[end]>tmp)
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		a[end + gap] = tmp;
	}
}

选择排序

基本思想：

每一趟（第i趟，i，...，n-2）在后面n-i个待排序的数据元素个数集合中选出关键码最小的数据元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素集合中只剩下1个元素，排序结束。

1.直接选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

复制代码
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
void Swap(int *x1, int *x2)
{
	int tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}
//选择排序
void SelectSort(int *a, int n)
{
	assert(a != NULL);
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int minindex = begin, maxindex = begin;
		int i = 0;
		for (i = begin; i <= end; ++i)
		{
			if (a[i]>a[maxindex])
				maxindex = i;
			if (a[i] < a[minindex])
				minindex = i;
		}
		Swap(&a[begin], &a[minindex]);
		if (begin == maxindex)
			maxindex = minindex;
		Swap(&a[end], &a[maxindex]);
		++begin;
		--end;
	}
}

 2.堆排序

  • 把堆顶array[0]元素和当前堆的最后一个元素交换
  • 堆元素个数减1
  • 由于第一步后根节点不再满足最堆定义，向下调整根结点

把一颗完全二叉树调整为堆，以及每次将堆顶元素交换后进行调整的时间复杂度均为O（log2n），所以堆排序的时间复杂度为：O（n*log2n）

复制代码
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
void AdjustDown(int *a, int n, int root)
{
	int parent = root;
	int child = root * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child]>a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
	}
}
//堆排序
void HeapSort(int *a, int n)
{
	assert(a != NULL);
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

 交换排序

1.冒泡排序

基本思想： 
设序列中有n个数据元素，循环进行n-1趟如下排序： 
第1趟：依次比较相邻两个数据元素(i = 0,1,2,…, n-2),若array[i]>array[i+1],则交换两个元 
素，否则不交换，这样数值最大的数据元素将被防止在a[n-1]中； 
第2趟：数据个数减1，即数据元素个数为n-1，操作方式和1类似，排完之后数据序列中的次大元素 
保存在array[n-2]中； 
当n-1趟结束时，排序结束。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//冒泡排序
void BubbleSort(int *a, int n)
{
	assert(a != NULL);
	int end = n;
	while (end > 0)
	{
		for (int i = 1; i > end; ++i)
		{
				if (a[i - 1]>a[i])
				{
					Swap(a[i - 1], a[i]);
					//flag = true;
				}
		}
		--end;
	}
}

 2.快速排序

基本思想：
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

递归

复制代码
1
2
3
4
5
6
7
8
9
int QuickSort_OP(int *a, int begin, int end)//递归
{
	if (begin < end)
	{
		int div = PartSort03/02/01(a, begin, end);
		QuickSort(a, begin, div-1);
		QuickSort(a, div+1, end);
	}
}

非递归

复制代码
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
int QuickSort(int *a, int left, int right)
{
	Stack st;
	StackInit();
	StackPush(&st, left);
	StackPush(&st, right);
	while (!StackEmpty())
	{
		int end = StackTop(&st);
		StackPop(&st);
		int begin = StackTop(&st);
		StackPop(&st);
		int div = PartSort01(a, begin, end);
		if (begin < div - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, div - 1);
		}
		if (end > div + 1)
		{
			StackPush(&st, div + 1);
			StackPush(&st, end);
		}
		
	}
}

 

 

第一种：左右指针法

每次选一个基准值，这里简单起见，直接每次取要排序区域的最后一位数据作为基准值。
设置两个指针，begin指针 指向要排序区域的起始位置，end指针 则指向要排序区域的最后位置。
begin指针寻找比基准值大的元素，end指针寻找比基准值小的元素。
交换begin 指针与end 指针的内容。
退出循环后，交换基准值与结束时begin,end指针所指向的值。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int PartSort01(int *a, int n,int begin, int end)
{
	//int begin = 0, end = n - 1;
	int key = a[end];
	int keyindex = end;
	
	while (begin < end)
	{
		while (begin < end&&a[begin] <= key)//找大
			begin++;
		while (begin < end&&a[begin] >= key)//找小
			end--;
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyindex]);
	return begin; 
}

 第二种： 挖坑法

每次选一个基准值，这里简单起见，直接每次取要排序区域的最后一位数据作为基准值。
设置两个指针，begin指针 指向要排序区域的起始位置，end指针 则指向要排序区域的最后位置。
begin指针寻找比基准值大的元素，将begin指针所指的值放入key的位置上。
end指针寻找比基准值小的元素，将end指针所指向的值放入空出的位置上。
退出循环后，最后将key值填入空出的位置上。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int PartSort02(int *a, int begin, int end)
{
	assert(a != NULL);
	int key = a[end];
	while (begin < end)
	{
		while (begin < end&&a[begin] <= key)//找大
		{
			begin++;
			a[end] = a[begin];
		} 		
		while (begin < end&&a[begin] >= key)//找小
		{
			end--;
			a[begin] = a[end];
		}		
	}
	a[begin] = key;
	return begin; 
}

第三种：前后指针法

定义两个指针，一前一后，cur（前）指向起始位置，prev（后）指向cur的前一个位置；选择数组最后一个元素作为key（right）
实现过程：cur找比key小的数，prev在cur没有找到的情况下，一直不动（即保证prev一直指向比key大的数）；直到cur找到比key小的数（+ +prev && prev != cur时）然后++cur,prev仍然不动。
直到cur走到right前一个位置，终止循环。最后++prev，交换prev和right的值。返回中间位置prev。最后再继续递归。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int PartSort03(int * a, int begin, int end)
{
	int prev = begin - 1;
	int cur = begin;
	int key = a[end];
	while (cur < end)
	{
		if (a[cur] < key&&++prev != cur)//找小
			Swap(&a[cur], &a[prev]);
			++cur;		
	}
	Swap(&a[++prev], &a[end]);
	return prev;
}

第四种  三数取中法

在待排序序列的第一个元素，中间元素和最后一个元素中取大小位于中间的那个元素。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//三数取中法
int GetmidIndex(int *a, int begin, int end)
{
	int mid = begin + ((end - begin) >> 1);
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if (a[begin] < a[end])
			return a[end];
		else
			return a[begin];
	}
	else
	{
		if (a[end] < a[mid])
			return mid;
		else if (a[begin < a[end]])
			return begin;
		else
			return end;
	}
}

 

 

归并排序

基本思想：
基本思想：将待排序的元素序列分成两个长度相等的子序列，为每一个子序列排序，然后将他们合并成一个序列。合并两个子序列的过程称为两路归并。

复制代码
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
//归并排序
void MergeSort(int *a, int n)
{
	assert(a != NULL);
	int *tmp = (int *)malloc(sizeof(int)*n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}
void _MergeSort(int *a, int begin, int end, int *tmp)
{
	int mid = begin + ((end - begin) >> 1);
	_MergeSort(a, begin, mid , tmp);
	_MergeSort(a, mid + 1, end, tmp);
	Merge(a, begin, mid, mid + 1, end, tmp);
}
void Merge(int *a, int begin1, int begin2, int end1, int end2, int *tmp)
{
	int index = begin1;
	int n = end2 - begin1;
	int start = begin1;
	while (begin1 < end1&&begin2 < end2) //从头开始比较大小，小的放在新空间中，继续往后走
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	while (begin1 < end1)//将a[begin1]-a[end1]的元素放入新空间中
		tmp[index++] = a[begin1++];
	while (begin2 < end2)
		tmp[index++]=a[begin2++];
	memcpy(a + start, start, sizeof(int)*(n + 1));
}

 计数排序

利用哈希的方法，将每个数据出现的次数都统计下来。哈希表是顺序的，所以我们统计完后直接遍历哈希表，将数据再重写回原数据空间就可以完成排序。

复制代码
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
//计数排序
void CountSort(int *a, int n)
{
	assert(a != NULL);
	int max = a[0], min = a[0];
	int i = 0;
	for (; i < n; ++i)
	{
		if (a[i]>max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	int *counts = (int*)malloc(range*sizeof(int));
	memset(counts, 0, sizeof(int)*range);
	for (i = 0; i < n;++i)
	{
		//1 2 1 4 1 1 9
		counts[a[i] - min]++; //counts[]++为统计原数组中数字出现的次数
	}
	int index = 0;
	for (i = 0; i < range; ++i)
	{
		while (counts[i]--)
		{
			a[index++] = i + min;
		}
	}
}

 排序算法的稳定性

如果在元素序列中有两个元素R[i]和R[j]，他们的排序码K[i]==K[j]，且在排序之前，R[i]在R[j]前面。若在排序后，R[i]仍然在R[j]前面，则称这个算法是稳定的。否则，这个算法是不稳定的。

最后

以上就是生动世界最近收集整理的关于各种排序算法的实现的全部内容，更多相关各种排序算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(74)

相关文章

Java笔记6.1
Java笔记6.1
排序算法的实现与比较
排序算法的实现与比较
排序算法实现与比较插入排序
排序算法实现与比较插入排序
java-Android-常用十大排序算法
java-Android-常用十大排序算法
各种排序算法的实现
各种排序算法的实现
排序算法实现及比较排序算法比较一、数组形式排序二、链表形式的排序三、常用的排序 API 与数据结构
排序算法实现及比较排序算法比较一、数组形式排序二、链表形式的排序三、常用的排序 API 与数据结构
各种排序算法的实现与比较各种排序算法的实现和比较
各种排序算法的实现与比较各种排序算法的实现和比较
java排序算法之快速排序
java排序算法之快速排序

评论列表共有 0 条评论

立即
投稿
返回
顶部