简单的内排序

发布于：2022-12-26 ⋅ 阅读:(452) ⋅ 点赞:(0)

  1.插入排序

1.1直接插入排序

将一组数据分成有序区和无序区

然后将无序区中第一个元素和有序区从大到小依此比较并交换

#include<stdio.h>
void InsertSort(int* arr, int n)
{
	for (int i = 0; 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;
	}
}

void PrintInsertSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	InsertSort(arr, sizeof(arr) / sizeof(int));
	PrintInsertSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度O(n^{2}) 

 1.2折半插入排序

 利用一组有序数组的下标取去中间值与无序数组第一个元素比较

依此递归

具体过程看：(9条消息) 【排序】折半插入排序_Adelaide_Guo的博客-CSDN博客_折半插入排序https://blog.csdn.net/Adelaide_Guo/article/details/82149098?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166052390616782388095140%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166052390616782388095140&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-1-82149098-null-null.142%5Ev40%5Epc_search_integral,185%5Ev2%5Econtrol&utm_term=%E6%8A%98%E5%8D%8A%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%8A%A8%E5%9B%BE&spm=1018.2226.3001.4187

#include<stdio.h>
void BinInsertSort(int* arr, int n)
{
	for (int i = 1; i < n;  i++)
	{
		int low = 0;
		int hight = i - 1;
		int temp = arr[i];
		while (low<=hight)               //递归
		{
			int mid = (low + hight) / 2;
			if (arr[mid] > temp)
			{
				hight = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		for (int j = i - 1; j > hight; j--)
		{
			arr[j + 1] = arr[j];
		}
		arr[hight + 1] = temp;
	}
}

void PrintBinInsertSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	BinInsertSort(arr, sizeof(arr) / sizeof(int));
	PrintBinInsertSort(arr, sizeof(arr) / sizeof(int));
	return 0;

时间复杂度： O(n^{2}) 

1.3希尔排序

按间隔比较排序

#include<stdio.h>
void ShellSort(int* arr, int n)
{
	int d = n / 3;
	while (d>0)
	{
		for (int i = 0; i < n-d ; ++i)
		{
			int end = i;
			int tmp = arr[end + d];
			while (end >= 0)
			{
				if (arr[end] > arr[end + d])
				{
					arr[end + d] = arr[end];
					end = end - d;
				}
				else
				{
					break;
				}
				
			}
			arr[end + d] = tmp;
			
		}
		d = d / 2;
	}
}

void PrintShellSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	ShellSort(arr, sizeof(arr) / sizeof(int));
	PrintShellSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

 时间复杂度：O(n^{1.5})

2.交换排序

2.1冒泡排序

两个元素比较，依此递推，将最大或者最小排的后面

#include<stdio.h>
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = 0; j < n - i - 1; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

void PrintBubbleSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	BubbleSort(arr, sizeof(arr) / sizeof(int));
	PrintBubbleSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度： O(n^{2})  

2.2快速排序

取一元素将大于该元素放一边小于该元素放另一边

依此递归

#include<stdio.h>
void QuickSort(int* arr, int left,int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;
	int pivot = begin;
	int key = arr[begin];
	while (begin<end)
	{
		while (begin<end && arr[end]>=key)
		{
			--end;
		}

		arr[pivot] = arr[end];
		pivot = end;


		while (begin < end && arr[begin] <= key)
		{
			++begin;
		}

		arr[pivot] = arr[begin];
		pivot = begin;
	}
	pivot = begin;
	arr[pivot] = key;
	QuickSort(arr, left, pivot - 1);
	QuickSort(arr, pivot + 1, left);
}

void PrintQuickSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	QuickSort(arr, 0,(sizeof(arr) / sizeof(int))-1);
	PrintQuickSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度： O（n{log_2{n}}^{}）

3.选择排序

3.1简单选择排序

将一组数组分为有序区间（开始可以只有一个元素）和无序区间

然后在无序区间中找到该区间最大或者最小值

将该值与有序区间中依此比较并插入

#include<stdio.h>
void SelectSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int k = i;
		for (int j = i + 1; j < n; ++j)       //类似快慢指针
		{
			if (arr[j] < arr[k])
				k = j;
		}
		if (k != i)
		{
			int tmp = arr[i];
			arr[i] = arr[k];
			arr[k] = tmp;
		}
	}
}

void PrintSelectSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	SelectSort(arr ,sizeof(arr) / sizeof(int));
	PrintSelectSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度： O(n^{2})

3.2堆排序

堆排序条件：左右子树必须是大堆或者小堆

先建堆后向下调整算法排序

升序建小堆

降序建大堆

将数组以二叉树形式储存

#include<stdio.h>
PrintHeapSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
void AdjustDwon(int* arr, int n, int root)        //建堆
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child+1<n&&arr[child + 1] > arr[child])
		{
			++child;
		}
		if (arr[child] > arr[parent])
		{
			int tmp = arr[child];
			arr[child] = arr[parent];
			arr[parent] = tmp;
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int n)
{
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDwon(arr, n, i);         //从下向上建堆
	}
	int end = n - 1;
	while (end > 0)
	{
		int tmp = arr[0];
		arr[0] = arr[end];
		arr[end] = tmp;
		AdjustDwon(arr, end, 0);         //排序；
		--end;
	}
}
int main()
{
	int arr[] = { 5,4,1,2,3,6 };
	HeapSort(arr ,sizeof(arr) / sizeof(int));
	PrintHeapSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度： O（n{log_2{n}}^{}）

4.归并排序

4.1二路归并排序

可以看下面链接的简述 

http://t.csdn.cn/t7shphttp://t.csdn.cn/t7shp

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
void merge(int *arr, int low,int mid, int hight)
{
	int* arr1=	NULL;
	int i = low, j = mid + 1, k = 0;
	arr1 = (int*)malloc(sizeof(int) * (hight - low + 1));
	assert(arr1);
	while (i<=mid&&j<=hight)
	{
		if (arr[i] < arr[j])
		{
			arr1[k] = arr[i];
			++k;
			++i;
		}
		else
		{
			arr1[k] = arr[j];
			++k;
			++j;
		}
	}
	while (i <= mid)
	{
		arr1[k] = arr[i];
		++k;
		++i;
	}
	while (j <= hight)
	{
		arr1[k] = arr[j];
		++k;
		++j;
	}
	for (k = 0, i = low; i <= hight; ++i, ++k)
	{
		arr[i] = arr1[k];
	}
	free(arr1);
}
void MergeSort(int *arr, int low, int hight)
{
	int mid = 0;
	if (low < hight)
	{
		mid = (low + hight) / 2;
		MergeSort(arr, low, mid);
		MergeSort(arr, mid + 1, hight);
		merge(arr, low, mid, hight);
	}
}

void PrintMergeSort(int* arr,int  n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[] = { 5,4,1,2,3 ,6};
	MergeSort(arr ,0 , (sizeof(arr) / sizeof(int))-1);
	PrintMergeSort(arr, sizeof(arr) / sizeof(int));
	return 0;
}

时间复杂度： O（n{log_2{n}}^{}）

4.2三路归并排序

4.基数排序

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布