数据结构之排序算法

void shellsort(int* a, int n)
{
	int gap = 3;
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int key = a[end + gap];
		while (end >= 0)
		{
			if (key < a[end])
			{
				a[end + gap] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + gap] = key;
	}
	
}

void shellsort(int* a, int n)
{
	
	int gap = n;
	while (gap>1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int key = a[end + gap];
				while (end >= 0)
				{
					if (key < a[end])
					{
						a[end + gap] = a[end];
						end-=gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = key;
			}
		}
 
	}
}

void shellsort(int* a, int n)
{
	
	int gap = n;
	while (gap>1)
	{
		gap = gap / 3 + 1;
		
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int key = a[end + gap];
				while (end >= 0)
				{
					if (key < a[end])
					{
						a[end + gap] = a[end];
						end-=gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = key;
			}
 
	}
}

1. 希尔排序是对直接插入排序的优化。

2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就

会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的

希尔排序的时间复杂度都不固定

《数据结构(C语言版)》--严蔚敏
希尔排序的分析是一个复杂的问题,因为它的时间是所取"增量"序列的函数,这涉及
些数学上尚未解决的难题。因此,到目前为止尚未有人求得一种最好的增量序列,但大
量的研究已得出一些局部的结论。如有人指出,当增量序列为dIta[k]=25-6+1-1时,希
尔排序的时间复杂度为O(12312)其中t为排序趙数,1<k<t<log2(n+1)」。还有人在
大量的实验基础上推出
当刀在某个特定范围内,希尔排序所需的比较和移动次数为为
n1.3,当770时,可减少到7(10g27)201。增量序列可以有各种取法1,且需注意:应使增
量序列中的值没有除1之外的公因子,并且最后一个增量值必须等于1。
《数据结构-用面相对象方法与C++描述》---殷人昆

2. 选择排序

2.1.1 选择排序

思想就是便利找到一个最大一个最小最小放在起始位置最大放在最后的位置

代码实现：

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int maxindex = begin;
		int minindex = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[maxindex])
			{
				maxindex = i;
			}
			if (a[i] < a[minindex])
			{
				minindex = i;
			}
		}
		Swap(&a[begin], &a[minindex]);
		//这里我们要注意如果maxindex指向与begin相等时，换位之后maxindex要更新
		if (begin == maxindex)
			maxindex = minindex;
		Swap(&a[end], &a[maxindex]);
		begin++;
		end--;
	}
}

2.1.2 选择排序特性

2.2.1 堆排序

堆排序就是先建堆然后按照堆的删除把堆顶数据放到数组最后让后end减减向下调整就行

代码实现如下：

void AddjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 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 = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
	
}
//堆排序
void HeapSort(int* a, int n)
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AddjustDown(a, n, i);
	}
	int end = n - 1;
	while (end >= 0)
	{
		Swap(&a[0], &a[end]);
		AddjustDown(a, end, 0);
		end--;
	}
}

2.2.2 堆排序特性

3. 交换排序

3.1.1 冒泡排序

代码实现：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int falg = 1;
		for (int j = 0; j < n - 1 - i ;j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
			falg = 0;
		}
		if (falg == 1)
		{
			break;
		}
	}
}

3.1.2 冒泡排序的特性

3.2.1 快速排序

3.2.1.1 hoare版本

这里我们写的是单趟的逻辑

int PartSort1(int* a, int left, int right)
{
		int keyi = left;
		int begin = left;
		int end = right;
		while (begin < end)
		{
			while (begin < end && a[end] >= a[keyi])
			{
				end--;
			}
			while (begin < end && a[begin] <= a[keyi])
			{
				begin++;
			}
			Swap(&a[end], &a[begin]);
		}
		Swap(&a[begin], &a[keyi]);
		return begin;
}

3.2.1.2 挖坑法

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
		int key = a[left];
		int keyi = left;
		int begin = left;
		int end = right;
		while (begin < end)
		{
			while (begin < end && a[end] >= a[keyi])
			{
				end--;
			}
			a[keyi] = a[end];
			keyi = end;
			while (begin < end && a[begin] <= a[keyi])
			{
				begin++;
			}
			a[keyi] = a[begin];
			keyi = begin;
		}
		a[keyi] = key;
		return keyi;
}

3.2.1.3 前后指针法

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
		int key = a[left];
		int prev = left;
		int cur = prev + 1;
		while (cur <= right)
		{
			//这里当我们每次交换时prev先走是为了防止数组最左端的数据被覆盖
			if (a[cur] < key && ++prev!=cur)
			Swap(&a[cur], &a[prev]);
			cur++;
		}
		//这里注意要与数组的头一个序列的值交换
		Swap(&a[prev], &a[left]);	
	return prev;
}

3.2.2.1 快排的递归实现及优化

// 三数取中
int findmidi(int* a, int left, int right)
{
	int midi = (right - left) / 2 + left;
	if (a[left] >= a[midi])
	{
		if (a[midi] >=a[right])
		{
			return midi;
		}
		else if (a[right] >= a[midi])
		{
			if (a[left] <= a[right])
			{
				return left;
			}
			else
			{
				return right;
			}
		}
	}
	else//a[midi]>a[left]
	{
		if (a[right] >= a[midi])
		{
			return midi;
		}
		else if (a[right] <= a[midi])
		{
			if (a[right] >= a[left])
			{
				return right;
			}
			else
			{
				return left;
			}
		}
	}
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return ;
 
	if (right - left + 1 <= 10)
	{
		InsertSort(a + left, right - left + 1);
		return ;
	}
	else
	{
		int midi = findmidi(a, left, right);
		Swap(&a[midi], &a[left]);
		int mid = PartSort3(a, left, right);
		QuickSort(a, left, mid - 1);
		QuickSort(a, mid + 1, right);
	}
}

其中的三数其中发是为了防止数据有序的情况下效率退化

而在数据足够少时不用再递归了减少了递归次数优化了效率

3.2.2.2 快排的非递归实现

 //快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	Stack stack;
	StackInit(&stack);
	StackPush(&stack, right);
	StackPush(&stack, left);
	while (!StackEmpty(&stack))
	{
		int begin = StackTop(&stack);
		StackPop(&stack);
		int end = StackTop(&stack);
		StackPop(&stack);
		int mid = PartSort3(a, begin, end);
		if (mid + 1 < end)
		{
			StackPush(&stack, end);
			StackPush(&stack, mid + 1);
		}
		if (begin < mid - 1)
		{
			StackPush(&stack, mid - 1);
			StackPush(&stack, begin);
		}
	}
	StackDestroy(&stack);
}

就是利用栈来存每次递归的区间用栈模拟实现递归过程注意的是每次入栈应该是右区间先入再左区间

3.2.2 快速排序的特性

4. 归并排序

4.1 归并递归实现

void _MergeSort(int *a, int *tem, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = (right - left) / 2 + left;
	_MergeSort(a, tem, left, mid);
	_MergeSort(a, tem, mid+1, right);
	//下面要进行归并排序
	int j = left;
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int  end2 = right;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tem[j++] = a[begin1++];
		}
		else
		{
			tem[j++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tem[j++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tem[j++] = a[begin2++];
	}
	memcpy(a + left, tem + left, sizeof(int) * (right - left + 1));
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tem = (int*)malloc(sizeof(int) * n);
	int left = 0;
	int right = n - 1;
	_MergeSort(a, tem, left, right);
}

注意分区间为什么是以上的分法请看下图

如果[2,3]按照第一种则会一直递归造成栈溢出。

4.2 归并非递归实现

//归并排序非递归写法
void MergeSortNonR(int *a, int n)
{
	int* tem = (int*)malloc(sizeof(int) * n);
	if (tem == NULL)
	{
		perror("malloc faliue");
		return;
	}
	int gap = 1;
	while (gap <= n)
	{
		//gap是每组归并数据的数据个数
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			//第二组全都越界
			if (begin2 >= n)
			{
				break;
			}
			//第二组部分越界end2更新
			if (end2 >= n)
				end2 = n - 1;
 
				int j = begin1;
				while (begin1 <= end1 && begin2 <= end2)
				{
					if (a[begin1] < a[begin2])
					{
						tem[j++] = a[begin1++];
					}
					else
					{
						tem[j++] = a[begin2++];
					}
				}
				while (begin1 <= end1)
				{
					tem[j++] = a[begin1++];
				}
				while (begin2 <= end2)
				{
					tem[j++] = a[begin2++];
				}
			memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tem);
	tem == NULL;
}

这里我们注意的就是越界问题如果begin2越界说明此次归并不需要了end2越界说明第二组有部分数据需要归并end2更新。如果end1越界此时begin2一定越界直接退出for循环不用进行归并了

5. 非比较排序

5.1 计数排序

代码实现：其实就是一个简单的哈希映射

// 计数排序
void CountSort(int* a, int n)
{
	//申请一个计数数组
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	for (int i = 0; i < n; i++)
	{
		count[(a[i]-min)]++;
	}
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count);
	count = NULL;
}

5.2 基数排序

思想就是先按照最低位按照顺序先排接着一直到最高位这里我们只需要了解一下思想就行

5.3 桶排序

思想就是我们建立一个指针数组此时数组里面的元素是一个指向链表结点的指针。

我们便利原数组把最高位对应的数放到指针数组对应的下标比如78，就要放到B数组下标为7的那个数组元素里面如果再来一个76就进行尾插最后对链表排序。

6. 排序算法复杂度及稳定性

稳定性是指两个相同的数在排序前后的相对位置如果不变就是稳定反之则不稳定。

冒泡这里我们这里我们不分析了

选择排序假设6，6，2我们把6和2交换6的相对位置改变了就不稳定了

插入排序是稳定

希尔如果两个相同的数被分到不同的组就会不稳定

堆排如果都是2把2放到最后相对位置改变不稳定

归并排序就是我们在归并时如果相等我们就把左区间的那个值先放到数组中就稳定了

快速排序假设6，6，5我们把6和5交换就会不稳定了