数据结构初阶 —— 常见排序_数据结构排序

目录

一，直接插入排序

二，希尔排序（又称缩小增量法）

三，直接选择排序

四，堆排序

五，冒泡排序

六，快速排序

七，归并排序

八，计数排序（非比较排序）

九，基数排序（非比较排序）

---

排序：按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作；

稳定性：若存在多个具有相同关键字的对象，经过排序，其相对位置次序保持不变，则称此算法稳定；

内部排序：数据元素全部放在内存中的排序；

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内存之间移动数据的排序；

一，直接插入排序

逻辑思路：

• 把待排序的对象，按其值的大小逐个插入到一个有序序列中（已经排好序），直到所有对象插入完为止，得到一个新的有序序列；
• 即当插入第i个元素时，其前面元素已为有序序列，在依次与前面元素比较，直到找到插入位置插入为止，原位置元素按顺序后移；

特性：

• 元素越接近有序，此算法时间效率越高；
• 时间复杂度，$O(N^2)$；
• 空间复杂度，$O(1)$；
• 稳定性，稳定；

//直接插入法
void InsertSort(int* arr, int n)
{
	int i = 0;
	for (i; i < n - 1; i++)
	{
        //单次插入
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
				break;
		}
		arr[end + 1] = tmp;
	}
}

二，希尔排序（又称缩小增量法）

逻辑思路：

• 先选定一个整数gap，把待排序文件分成gap个组（距离为gap为一组），并对每个组进行直接插入排序，即预排序（已达到接近有序）；
• 重复上操作，但gap取到1时排序为止；

注：

• 数据一次挪动gap步，而不是一步，更快；
• gap越小，挪动后越接近有序，但也会越慢；
• gap为1时，其实就是直接排序；

特性：

• 希尔排序时对直接插入排序的优化；
• 时间复杂度，$O(N^1.3)$或$O(N^1.25)$~$O(1.6*N^1.25)$；
• 空间复杂度，$O(1)$； 
• 稳定性，不稳定；

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	//gap>1为预排序，gap=1为直接排序
	while (gap > 1)
	{
		//gap每三倍的逐渐减小，+1保证最后一次排序gap为1
		gap = gap / 3 + 1;
		//预排序(多组并排)
		int i = 0;
		for (i; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}
	}
}

三，直接选择排序

逻辑思路：

• 从待排序元素中，选出最大(或最小)的元素，交换到起始位置；
• 然后在剩余的元素中，重复上述操作，直到剩余一个元素为止；

特性：

• 此排序思路简单，但效率最差，实际中很少使用；
• 时间复杂度，$O(N^2)$；
• 空间复杂度，$O(1)$；
• 稳定性，不稳定；

//直接选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
				mini = i;
			if (arr[i] > arr[maxi])
				maxi = i;
		}
		Swap(arr + begin, arr + mini);
		//但首元素即为最大值时，此时值已被交换需校正
		if (begin == maxi)
			maxi = mini;
		Swap(arr + end, arr + maxi);
		begin++;
		end--;
	}
}

四，堆排序

逻辑思路：

• 利用堆的数据结构进行排序，通过堆进行选择数据，是选择排序的一种；
• 升序建大堆，降序建小堆；

特性：

• 时间复杂度，$O(N*logN)$
• 空间复杂度，$O(1)$；
• 稳定性，不稳定；

//建堆排序
void HeapSort(int* arr, int n)
{
	//建堆 - O(N)
	int i = (n - 1 - 1) / 2; //最后节点的父节点
	for (i; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
 
	//排序 - O(N*log(N))
	int end = n - 1;
	while (end)
	{
		Swap(arr, arr + end);
		AdjustDown(arr, end, 0);
		end--;
	}
}

五，冒泡排序

逻辑思路：

• 从首个元素开始，依次比较，将较大的值向后交换；
• 然后在剩余的元素中，重复上述操作，直到剩余一个元素为止；

特性：

• 首趟交换将最大值排到最后，次躺将次大值排到倒数第二个；
• 时间复杂度，$O(N^2)$；
• 空间复杂度，$O(1)$；
• 稳定性，稳定；

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(arr + j, arr + j + 1);
				exchange = 1;
			}		
		}
		if (!exchange) 
			break;
	}
}

六，快速排序

一种二叉树结构的交换排序；

逻辑思路：

• 任取某个元素为基准值（一般是头或尾），将序列分割成两个子序列，左序列所有元素均小于基准值，右子序列中所有元素均大于基准值；
• 然后左右子序列，重复上述操作，直到所有元素都排序到相应位置为止；

特性：

• 时间复杂度，$O(N^2)$，三数取中法$O(N*logN)$；
• 空间复杂度，$O(N*logN)$；
• 稳定性，不稳定；

按基准值将序列划分尾左右子序列方法：

• 左右指针法（Hoare）：
  • 如以左边首个元素为key；
  • 随后最右边right先向左走，遇到比key小的停下；
  • 在最左边left向右走，遇到比key大的停下；
  • 此时左右元素交换；
  • 然后重复操作，直到left等于right为止；
• 挖坑法：
  • 如以左边首个元素为key，并保存此元素；
  • 随后最右边right先向左走，遇到比key小的停下并将此元素填入key位置，此位置在标记为key；
  • 在最左边left向右走，遇到比key大的停下并将此元素填入key位置，此位置在标记为key；
  • 然后重复操作，直到left等于right为止，最后把最初key元素填入最后的key位置即可；
• 前后指针法：
  • 如以左边首个元素为key，此元素标记为前指针prev，下个元素标记为后指针cur；
  • cur先向后走，遇到比key小的停下，prev++，此时交换prev与cur位置的元素；
  • 然后重复操作，直到序列尾为止，最后交换key与prev位置元素即可；

//针对有序序列，时间复杂度为O(N^2)，会很大影响效率； 
//三数取中法
int GetMidIndex(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2; //(left+right)/2，left+right可能会溢出
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return right;
		else
			return left;
	}
	else
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[left] < arr[right])
			return left;
		else
			return right;
	}
}

//左右指针法
int PartSort(int* arr, int left, int right)
{
	int midi = GetMidIndex(arr, left, right);
	Swap(arr + left, arr + midi);
 
	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
			right--;
		while (left < right && arr[left] <= arr[keyi])
			left++;
		Swap(arr + left, arr + right);
	}
	Swap(arr + keyi, arr + left);
	return left;
}

//挖坑法
int PartSort(int* arr, int left, int right)
{
    //三数取中
    int midi = GetMidIndex(arr, left, right);
    Swap(arr + left, arr + midi);
 
	int keyi = left;
	int key = arr[keyi];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			right--;
		arr[keyi] = arr[right];
		keyi = right;
 
		while (left < right && arr[left] <= key)
			left++;
		arr[keyi] = arr[left];
		keyi = left;
	}
	arr[keyi] = key;
	return keyi;
}

//前后指针法
int PartSort(int* arr, int left, int right)
{
    //三数取中
	int midi = GetMidIndex(arr, left, right);
	Swap(arr + left, arr + midi);
 
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
			Swap(arr + prev, arr + cur);
		cur++;
	}
	Swap(arr + prev, arr + keyi);
	return prev;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left < right)
	{
		int keyi = PartSort(arr, left, right);
		QuickSort(arr, left, keyi - 1);
		QuickSort(arr, keyi + 1, right);
	}	
}

快速排序非递归 

逻辑思路：

• 递归方法为，每躺排序后，获得左右子序列区间，然后子序列在排；
• 非递归方法，即通过栈记录每躺排序后的子区间（入栈），然后在取此子区间排序，在记录此排序后的子区间（入栈）；

注：

• 递归太深，会容易导致栈溢出；
• 循环或栈+循环；

//快速排序非递归 
void QuickSortNonR(int* arr, int left, int right)
{
	Stack st; //创建栈st
	StackInit(&st); //初始化栈
	StackPush(&st, left); //记录区间（入栈）
	StackPush(&st, right); //记录区间（入栈）
 
	while (!StackEmpty(&st))
	{
		right = StackTop(&st);
		StackPop(&st);
		left = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort(arr, left, right);
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}
	StackDestroy(&st);
}

七，归并排序

逻辑思路：

• 原理为如有两有序序列，可直接合并为一个有序序列；
• 将待排序序列二分为左右两个子序列，如左右子序列不为有序，通过递归分解直到左右有序，在一一归并为有序即可；

特性： 

• 时间复杂度，$O(N*logN)$；
• 空间复杂度，$O(N)$；
• 稳定性，稳定；

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);
	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
    //排序
    int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[index++] = arr[begin1++];
		else
			tmp[index++] = arr[begin2++];
	}
	while(begin1 <= end1)
		tmp[index++] = arr[begin1++];
	while (begin2 <= end2)
		tmp[index++] = arr[begin2++];
	//最后还原到原数组
	for (int i = 0; i <= right; i++)
		arr[i] = tmp[i];
}
 
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

归并排序非递归 

• 循环，可倒循环；

//归并非递归排序
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
 
	int grpNum = 1;
	while (grpNum < n)
	{
		for (int i = 0; i < n; i += grpNum * 2)
		{
			//归并
			int begin1 = i, end1 = i + grpNum - 1;
			int begin2 = i + grpNum, end2 = i + grpNum * 2 - 1;
			//修正越界,设置为一个无效区间
			if (begin2 >= n)
			{
				begin2 = n + 1;
				end2 = n;
			}	
			if (end2 >= n)
				end2 = n - 1;
			//排序
			int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[index++] = arr[begin1++];
				else
					tmp[index++] = arr[begin2++];
			}
			while (begin1 <= end1)
				tmp[index++] = arr[begin1++];
			while (begin2 <= end2)
				tmp[index++] = arr[begin2++];
		}
		//最后还原到原数组
		for (int i = 0; i < n; i++)
			arr[i] = tmp[i];
 
		grpNum *= 2;
	}
}

八，计数排序（非比较排序）

逻辑思路：

• 统计原数组中，每个元素出现的次数，并记录于count数组内；
• 排序，遍历count数组，在原数组中对应位置填写该次数个元素；

特性： 

• 适合数据大小比较集中，且只适合整数排序(浮点和字符串不适合)；
• 时间复杂度，$O(max(N,Range))$；
• 空间复杂度，$O(Range)$；
• 稳定性，不稳定；

//计数排序
void CountSort(int* arr, int n)
{
    //获取最值
	int min = arr[0], max = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
    //相对映射
	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	//统计次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//排序,还原数组
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
			arr[i++] = j + min;
	}
}

九，基数排序（非比较排序）

省略！！！

有兴趣可自行搜索！！！