八大排序

程序员文章站 2022-03-15 08:39:03

...

一.冒泡排序（交换排序）

思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。（从头扫描待排序序列，第一趟排序，对n个记录进行排列，在扫描过程中顺次比较相邻的两个元素。若按升序排列，则把较小的数往前移动。接着进行第二趟排列，对n-1个记录进行排列，如此反复，直到排好序为止。）
时间复杂度：最好情况O(n) 最坏情况O(n^2) 平均情况O(n^2)
空间复杂度：O(1)
稳定性：稳定
代码及优化：

//冒泡法代码
void Bubble(int *arr, int len)
{
	int tmp = 0;
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1; j++)
		{
			if (arr[j]>arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
//冒泡法代码优化
void BubbleSort(int *arr, int len)
{
	bool swap = false;
	int tmp = 0;
	for (int i = 0; i < len-1; i++)
	{
		swap = false;
		for (int j = 0; j < len-i-1; j++)
		{
			if (arr[j]>arr[j+1])
			{
				tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
				swap = true;
			}
		}
		if (!swap)
		{
			return;
		}
	}	
}

6. 八大排序

冒泡：若为升序，每一趟排序中，则有都选出无序中一个最大的放在最后。即每一趟在无序中冒出一个最大的数在其最后面，执行len-1趟

二.直接选择排序（选择排序）

思想：通过n-i次关键字间的比较，从n-1+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。（从头扫描待排序序列，第一趟排序，对n个记录进行排序，用第一个和后面所有的依次进行比较。以升序排列为例，把较小的值换到第一个。第二趟排序，从第二个开始，对n-1个记录进行排序。进行n-1趟。）
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
代码及优化

void Choice(int *arr, int len)
{
	for (int i = 0; i < len-1; i++)
	{
		for (int j = i+1; j < len; j++)
		{
			if (arr[i]>arr[j])
			{
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

直接选择法：每一趟选出一个最小的数放在当前排序队列的第一位，进行n-1趟。

三. 直接插入排序（插入排序）

思想：将一个记录插入到已经排序的有序表中，从而得到一个新的，记录数增1的有序表。（以升序排列为例，若一个数字比他后面数字大，则则把大数后移，小数插入。以此类推，我们在移动的时候，比较一个数字，移动一个数字。）
时间复杂度：最好情况O(n) 最坏情况O(n^2) 平均情况O(n^2)
空间复杂度：O(1)
稳定性：稳定
代码及优化：

代码
void Insert_Sort(int*arr, int len)
{
	int tmp = 0;
	int i, j;
	for (i = 1; i < len; i++)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (tmp < arr[j])
			{
				arr[j + 1] = arr[i];
			}
			else break;
		}
		arr[j + 1] = tmp;
	}
}

优化见下个排序（希尔排序）

6. 八大排序

四.希尔（shell）排序（直接插入排序的优化）

思想：将待排序序列分为5组，然后让其各组分别排序（用直接插入排序）。由此得到的整个排序序列基本有序。再分为3组，让其各组排序。再分为1组，让其排序。最后就得到一个顺序的数组。
时间复杂度：最好情况O(n) 最坏情况O(n^2) 平均情况O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定

代码及优化：

代码
void Shell(int *arr, int len,int gap)
{
	int tmp=0;
	int i, j;
	for (i = gap; i < len; i++)
	{
		tmp = arr[i];
		for (j = i - gap; j >= 0; j=j-gap)
		{
			if (arr[j]>tmp)
			{
				arr[j + gap] = arr[j];
			}
			else break;
		}
		arr[j + gap] = tmp;
	}
}
 void ShellSort(int *arr, int len)
{
	int brr[] = { 5, 3, 1 };
	int lenn = sizeof(brr) / sizeof(brr[0]);
	for (int i = 0; i < lenn; i++)
	{
		Shell(arr, len, brr[i]);
	}
}

首先分为5组，用直接插入排序先将各组进行排序。然后将整体分为3组，同样对各组进行排序。最后将整体进行排序。目的是为了减少排序的次数

五.堆排序（选择排序）

思想：将待排序序列构造成一个大根堆，此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
时间复杂度：O(nlog2 n)
空间复杂度：O(1)
稳定性：不稳定

代码及优化

void Adjust(int *arr, int start, int end)//调整树的根结点
{
	int tmp = arr[start];
	for (int i = 2*start+1; i <= end; i = 2 * i + 1)
	{
		if (i < end&&arr[i] < arr[i + 1])
		{
			i++;
		}
		if (tmp < arr[i])
		{
			arr[start] = arr[i];
			start = i;
		}
		if (tmp>arr[i])
		{
			break;
		}
	}
	arr[start] = tmp;
}
void HeapSort(int *arr, int len)
{
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)//第一次建立大根堆
	{
		Adjust(arr, i, len - 1);
	}
	//交换,并建立大根堆
	int tmp = 0;
	for (int i = 0; i < len - 1; i++)
	{
		tmp = arr[0];
		arr[0] = arr[len - 1 - i];
		arr[len - 1 - i] = tmp;
		Adjust(arr, 0, len - 1-i-1);
	}
}

建立大根堆。-----首先将未排序序列建立大根堆，然后将根结点的数和未排列的最后一位数交换，并在未排序序列重新建立大根堆。依次循环。

八大排序

六.归并排序

思想：先使每个子序列有序，再使子序列段间有序。
时间复杂度：O(nlog2 n)
空间复杂度：O(n)
稳定性：稳定
代码及优化：

//归并
void Merge(int *arr, int len, int gap)
{
	int *brr = (int*)malloc(sizeof(int));
	int start1 = 0;
	int end1 = start1 + gap - 1;
	int start2 = end1 + 1;
	int end2 = start2 + gap - 1;
	int i = 0;
	while (start2 < len)
	{
		while (start1 <= end1&&start2 <= end2)//两段都有数据
		{
			if (arr[start1] <= arr[start2])
			{
				brr[i++] = arr[start1++];
			}
			else
			{
				brr[i++] = arr[start2++];
			}
		}
		while (start1 <= end1)
		{
			brr[i++] = arr[start1++];
		}
		while (start2 <= end2)
		{
			brr[i++] = arr[start2++];
		}
		start1 = end2++;
		end1 = start1 + gap - 1;
		start2 = end1++;
		end2 = start2 + gap - 1;
	}
	while (start1 < len)
	{
		brr[i++] = arr[start1++];
	}
	for (i = 0; i < len; i++)
	{
		arr[i] = brr[i];
	}
	free(brr);
	brr = NULL;
}
void MergeSort(int *arr, int len)
{
	for (int i = 1; i < len; i*=2)
	{
		Merge(arr, len, i);
	}
}

八大排序

七.基数排序

思想：按最低位的值进行记录进行初步排序，在此基础上按照次低位的值进行进一步排序。
时间复杂度：最好情况O(d(r+n)) 最坏情况O(d(r+n)) 平均情况O(d(r+n))
空间复杂度：O(rd+n)
稳定性:稳定

代码及优化：

//删除第一个节点DelFirst()
bool DelFirst(List plist,int *rtv)
{
	Node *pDel = plist->next;
	if(pDel == NULL)
	{
		return false;
	}
	plist->next = pDel->next;
	*rtv = pDel->data;
	free(pDel);
	pDel = NULL;
	return true;
}
int GetMaxBit(int *arr,int len)
{
	//1、找出数组当中最大的数字
	int max = arr[0];
	for(int i = 1;i < len;i++)
	{
		if(arr[i] > max)
		{
			max = arr[i];
		}
	}
	//2、求最大的数字的位数
	int count = 0;
	while(max != 0)
	{
		count++;
		max/=10;
	}
	return count;
}

int GetNum(int num,int figure)
{//123%10      123/10 = 12  12%10 = 2  
	for(int i = 0;i < figure;i++)
	{
		num/=10;
	}
	return num%10;
}

void Base(int *arr,int len,int figure)
{
	Node head[10];
	int i;
	for(i = 0;i < 10;i++)
	{
		InitList(&head[i]);
	}
	int tmp;
	//得到数组当中的每一个数字，得到当前数字的figure为
	for(i = 0;i < len;i++)
	{
		//1、figure位
		tmp = GetNum(arr[i],figure);//123   3
		//2、入桶：figure桶
		InsertTail(&head[tmp],arr[i]);
	}
	//出桶
	i = 0;
	for(int j = 0;j < 10;  )
	{
		if(DelFirst(&head[j],&arr[i]))
		{
			i++;
		}
		else
		{
			j++;
		}
	}
}
void BaseSort(int *arr,int len)
{
	//1、入桶的次数(数组当中最大的数字的位数)
	int count = GetMaxBit(arr,len);
	//2、得到入桶次数后进行如同
	for(int i = 0;i < count;i++)//d代表的是：入桶的次数
	{
		Base(arr,len,i);//i:代表位数  0代表右数第一位  个位
	}
}

八.快速排序（交换排序）

思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
时间复杂度：平均情况【O(nlog2 n)】最好情况【O(nlog2 n)】最坏情况【O(n^2)】
空间复杂度：O(log2 n)
稳定性：不稳定

代码及优化

int Partion(int*arr, int low, int high)
{
	int tmp = arr[low];
	while (low < high)
	{
		while (low < high&&arr[high] >= tmp)
		{
			high--;
		}
		if (low >= high)
		{
			break;
		}
		else
		{
			arr[low] = arr[high];
		}
		while (low < high&&arr[low] <= tmp)
		{
			low++;
		}
		if (low >= high)
		{
			break;
		}
		else
		{
			arr[high] = arr[low];
		}
	}
	arr[low] = tmp;
	return low;
}

void swap(int *arr, int low, int high)
{
	int tmp = arr[low];
	arr[low] = arr[high];
	arr[high] = tmp;
}       
//优化二   三分取基准
void SelectPivotMedianOfThree(int *arr, int low, int mid, int high)//4  1  8
{
	if (arr[low] < arr[mid])
	{
		swap(arr, low, mid);
	}
	if (arr[high] < arr[mid])
	{
		swap(arr, low, mid);
	}
	if (arr[low] > arr[high])
	{
		swap(arr, low, high);
	}
}
  //优化4  相同元素聚集法
void Focus_Same_Num(int *arr, int low, int par, int high, int *left, int *right) 
{
	if(low < high)
	{
		int ParLeftIndex = par-1;
		int ParRightIndex = par+1;
		for(int i = par-1;i >= low;i--)
		{
			if(arr[i] == arr[par] )//如果两个值相等，那么交换，如果不是紧挨着的
			{
				if(i != ParLeftIndex)
				{
				      Swap(arr,i,ParLeftIndex);//把相等的拉过来，聚集在一起
				      ParLeftIndex--;
				}
				else
				{
			        	ParLeftIndex--;
				}
				
			}
		}
		*left = ParLeftIndex;

		for(int i = par+1;i <= high;i++)
		{
			if(arr[i] == arr[par])
			{
				if(i != ParRightIndex)
				{
					Swap(arr,i,ParRightIndex);
					ParRightIndex++;
				}
				else
				{
					ParRightIndex++;
				}
			}
		}
		*right = ParRightIndex;
	}
}
void Quick(int*arr, int start, int end)
{
	int par = Partion(arr, start, end);
	int left = par - 1;
	int right = par + 1;
	if (par < end - 1)
	{
		Quick(arr, right, end);
	}
	if (par>start + 1)
	{
		Quick(arr, start, left);
	}
}
void Quick_sort(int* arr, int len)
{
	Quick(arr, 0, len - 1);
}

（1）一趟快排，返回基准。序列基本有序(基准左边都比他小，右边都比他大)

八大排序

（2）基准两边继续寻找进行排序，直到right==end且left==start。

八大排序

八大排序

一.冒泡排序（交换排序）

二.直接选择排序（选择排序）

三. 直接插入排序（插入排序）

四.希尔（shell）排序（直接插入排序的优化）

五.堆排序（选择排序）

六.归并排序

七.基数排序

八.快速排序（交换排序）

java实现ArrayList根据存储对象排序功能示例

java根据List内对象的属性排序方法

在ASP.NET 2.0中操作数据之四十三：DataList和Repeater数据排序（二）

在ASP.NET 2.0中操作数据之四十二：DataList和Repeater数据排序（一）

在ASP.NET 2.0中操作数据之四十四：DataList和Repeater数据排序（三）

老生常谈比较排序之堆排序

C#排序算法的比较分析

Android recyclerview实现拖拽排序和侧滑删除

C#实现Datatable排序的方法

C#实现的二维数组排序算法示例