首页 > 其他分享 >排序（前篇）

排序（前篇）

时间：2024-05-29 20:30:30浏览次数：26  
标签：tmp 前篇 end int gap sizeof 排序

1.排序的概念及其运用

2.插入排序的概念及实现

3.希尔排序的概念及实现 

4.选择排序概念及实现

总代码（对比各个排序在大量的数据情况排序所化的时间）：

1.排序的概念及其运用

1.1排序的概念


排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

1.2排序的运用

在网上购物时，会出现综合，销量及评论数等，会以此为参考来排序，选出综合最高，销量最高的产品，以及院校排名这些，都使用了排序。

（以下图片仅参考）

1.3 常见的排序算法

2.插入排序的概念及实现

2.1插入排序的概念

就像扑克牌一样，每拿到一张牌都要放进已经排好序的牌里面，用这张牌跟里面的比较，再把这张牌放到合适的位置，插入排序的原理就是把数插入已经排好序的数里面，比较排好数的里面的每一个数，找到位置就插入。

代码：

#include<stdio.h>
void InsertSort(int* a,int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end+1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
int main()
{
	int a[10] = { 3,4,5,1,2,6,7,8,2 };
	int size = sizeof(a) / sizeof(a[0]);
	InsertSort(a,size);
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

代码分析： 

while循环出去有俩种情况，1是触发break，二是while循环的条件不满足，在循环外把tmp赋给数组下标为end+1的位置， 是因为如果是while循环结束的话刚好也可以赋值，但是在里面的话，因为while结束的就无法把数据加回去（移动带来覆盖，会有一位重复，需要赋值来填回去）。

（动态图关于插入排序24年-05月27日--排序/动图/插入排序.gif · 比特杭哥/113期 - Gitee.com）

2.2冒牌排序的时间复杂度

冒泡排序的最坏情况：

假设if条件每次都会执行，那么时间复杂度就为O(N^2).

最好的情况：

上面冒泡代码不能做到O(N),需要对其优化才能使冒泡排序达到最好情况，

设置一个flag去判断是否触发了if条件，如果触发了就置为0，后面再去检验值是否为一开始的初始值，是就说明没有触发if条件，没触发就说明顺序是排好的，只执行了里面的if判断，所以时间复杂度是O(N)。

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

2.3插入排序的时间复杂度

按照最坏打算：

既逆序情况

最好的情况：

当数据是以升序排序时，里面的循环不执行（会从break跳出），则只有for循环执行，所以时间复杂度就为O(N)。

插入排序与冒泡排序的时间复杂度虽然是一样的，但插入排序是比冒泡排序好，因为插入排序最坏的情况很难达到，只有是逆序（或者接近这个情况）的情况下，插入排序才会慢下来，而冒泡排序一般都是O(N^2),因为冒泡每次遍历选出其中最大的放最后，if的条件任意触发。

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

3.希尔排序的概念及实现 

3.1希尔排序概念

希尔排序与插入排序密不可分，基于插入排序来实现希尔排序的。

希尔排序：首先会对数据进行预排序（让数组接近有序），再进行插入排序（因为插入排序怕的是数组是逆序情况）。

预排序：把数组在逻辑上分成gap组，gap是间隔的距离，然后对每个gap组进行插入排序，这样可以使大的数据跑到比较后面的位置，小的数据会跑到比较前面的位置，gap设置的越大，大的数据越快到后面，小的数据越快到前面，越不接近有序，gap设置的越小，数据跳的慢，但是会越接近有序的情况，gap为1的时候就是插入排序了，希尔排序就是慢慢把gap的值调小（设置gap是为了最后一次gap为一做铺垫，为了插入排序能更快的完成），最后gap为一时执行插入排序。

3.2希尔排序的代码实现

代码实现1：

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void ShellSort1(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 tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					swap(&a[end], &a[end + gap]);
					end--;
				}
				else
					break;

			}
			a[end + gap] = tmp;

		}
	}
}

代码实现二：

void ShellSort2(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 tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						swap(&a[end], &a[end + gap]);
						end -= gap;
					}
					else
						break;

				}
				a[end + gap] = tmp;

			}
		}
	}
}

代码分析：上面俩个代码的样子不一样，但是效率是一样的俩种都可以使用，

n是数组的个数，一般gap的值都为个数的三分之一+1，加一是为了最后gap的值能达到一进行插入排序，gap/2的效率不如gap/3（大量数据实验得出的），代码一是多个gap组同时进行预排序，每次i加一，但是比的是gap距离的数据，gap第一组的第一个跟其gap距离的比完后，第二个gap组的第一个跟其gap距离的比，再到第三个gap组的第一个与其gap距离的数据比较，再到第二个等等，代码二则是第一个gap组会一直比完才到第二个gap组比。还需要注意的是循环终止条件是n-gap，是因为循环里面有end+gap，n+gap-gap刚好是为n，也就是数组最后一个数据下标的下一个，有效数据的下一个是不能访问的，会造成越界访问，数组最多能访问到n-1的位置，如果是i<n，则a[end+gap]就会越界了。

3.3希尔排序的时间复杂度（简单分析）

希尔排序的时间复杂度为O(N^1.3)。

4.选择排序概念及实现

选择排序就是遍历数组找到最小的数据并把它放在最前面，可以对它进行优化，就是在遍历的同时把最大和最小的数据找出来并放在俩边

代码实现：

void SelectSort(int* a, int n)
{
	int begin, end;
	begin = 0;
	end = n - 1;
	while (begin < end)
	{
		int mini, max;
		mini = max = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[max] < a[i])
			{
				max = i;
			}
		}
	
		swap(&a[mini], &a[begin]);
		swap(&a[max], &a[end]);
		end--;
		begin++;
	}	
}

代码分析：

因为是找最大和最小并放在俩边，所以begin和end会慢慢往中间靠近，在定义最小值和最大值去和数组的每一个数比较，比定义的最大值大就交换一下下标，比最小值小就交换 下标，遍历完后在交换值，并且把begin++和end--，因为begin和end都放好了对应的值，要放其它位置的值。

总代码（对比各个排序在大量的数据情况排序所化的时间）：

test.c文件：

#include"Sort.h"

void TestInsertSort()
{
	int a[] = { 2,4,1,7,8,3,9,2 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestShellSort()
{
	int a[] = { 9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5 };
	//InsertSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));

	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestSelectSort()
{
	//int a[] = { 9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5,9,1,2,5,7,4,6,3,5 };
	//InsertSort(a, sizeof(a) / sizeof(int));
	//int a[] = { 2,4,1,7,8,3,9,2 };
	int a[] = { 9,1,2,5,7,4,6,3 };

	PrintArray(a, sizeof(a) / sizeof(int));
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand()+i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	//InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	//QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	//BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}


int main()
{
	//TestInsertSort();
	//TestShellSort();
	TestSelectSort();

	//TestOP();

	return 0;
}

Sort.h文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void PrintArray(int* a, int n);

// 有实践意义
void InsertSort(int* a, int n);

void ShellSort(int* a, int n);

void ShellSort(int* a, int n);

void HeapSort(int* a, int n);

// 适合教学，实践中没啥价值
void BubbleSort(int* a, int n);

void SelectSort(int* a, int n)

Sort.c文件：

#include"Sort.h"

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

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 时间复杂度：O(N^2)  什么情况最坏：逆序
// 最好：顺序有序，O(N)
// 插入排序
void InsertSort(int* a, int n)
{
	//  [0, n-1]
	for (int i = 0; i < n - 1; i++)
	{
		// [0, n-2]是最后一组
		// [0,end]有序 end+1位置的值插入[0,end]，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

// O(N^1.3)
//void ShellSort(int* a, int n)
//{
//	/*int gap = 3;
//	for (int j = 0; j < gap; j++)
//	{
//		for (size_t i = j; i < n - gap; i += gap)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//	}*/
//
//	int gap = n;
//	while (gap > 1)
//	{
//		// +1保证最后一个gap一定是1
//		// gap > 1时是预排序
//		// gap == 1时是插入排序
//		gap = gap / 3 + 1;
//
//		for (size_t i = 0; i < n - gap; ++i)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//		//printf("gap:%2d->", gap);
//		//PrintArray(a, n);
//	}
//}

// O(N ^ 1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;

		for (size_t i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}


void AdjustDown(int* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	while (child < n)  // 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;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	// 向下调整建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

// O(N^2) 最坏
// O(N)   最好
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		// 单趟
		int flag = 0;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}

		if (flag == 0)
		{
			break;
		}
	}
}

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}

			if (a[i] < a[mini])
			{
				mini = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

标签：tmp,前篇,end,int,gap,sizeof,排序
From： https://blog.csdn.net/2302_80378107/article/details/139277152

相关文章

  • oracle的排序函数以及mysql使用变量实现排序
    oracle的排序函数rank()函数：跳跃排序，如果两个第一，则后边是第3dense_rank()函数：连续排序，，再如两个第一，则后边是第2row_number()函数：连续排序，没有并列的情况createtableccx_test( coursevarchar(10), scoreint);insertintoccx_testvalues(1,70);insertintoccx_......
  • react使用antd实现表格的时间排序
    importReactfrom'react';import{Table}from'antd';importmomentfrom'moment';constdata=[{key:'1',date:'2018-01-11T12:00:00Z',},{key:'2',date:'2......
  • 快速排序的实现
    目录一、递归        1、霍尔法：2、挖坑法：3、前后指针法：二、非递归三、完整代码：基本思想：先取这个待排序元素序列中的某一个元素最为key值，然后通过这个key值将这个序列分为两边，一边小于这个key，另一边大于这个key，然后接着对这个左边的序列和右边的序列进行相......
  • sql涉及姓名排序--2种排序选择
    第一种：按字符的编码值（ASCII或Unicode值）进行排序ORDERBYscoreDESC,SUBSTR(stuName,1,1)DESC；Oracle会比较`stuName`的第一个字符的编码值（ASCII或Unicode值）来决定顺序。第二种：按照姓氏的拼音顺序进行排序ORDERBYscoreDESC,NLSSORT(SUBSTR(stu......
  • leetCode.82. 删除排序链表中的重复元素 II
    leetCode.82.删除排序链表中的重复元素II题目思路：代码classSolution{public:ListNode*deleteDuplicates(ListNode*head){autodummy=newListNode(-1);dummy->next=head;autop=dummy;while(p->next){......
  • 希尔排序(详讲)
    目录个人评价原理希尔排序分为两步例如间隔大小时间复杂度代码个人评价一个很天才的想法，对插入排序进行一点更改，代码很简略但是非常的快和堆排序可以坐在一张桌上原理一般的插入排序都是以1为单位进行比较越有序，插入排序越快希尔排序就是一个使数组不断趋近有......
  • 【LeetCode算法】第83题：删除排序链表中的重复元素
    目录一、题目描述二、初次解答三、官方解法四、总结一、题目描述二、初次解答1.思路：双指针法，只需遍历一遍。使用low指向前面的元素，high用于查找low后面与low不同内容的节点。将具有不同内容的节点链接在low后面，实现重复元素的删除。2.代码：/***Definitionfor......
  • 八大基础排序
    八大基础排序1.冒泡排序（BubbleSort）基本思想：依次比较相邻的两个元素，若它们的顺序错误则进行交换。特点：稳定排序，但效率较低，时间复杂度为O(n^2)，空间复杂度为O(1)。代码实例publicclassBubbleSortExample{publicstaticvoidmain(String[]args){//示......
  • 数据结构的直接插入排序（C语言版）
    一.直接插入排序的基本概念1.直接插入排序的基本思想将数组分为已排序和未排序两部分。每次从未排序部分取出一个元素,将其插入到已排序部分的合适位置,使得已排序部分保持有序。重复步骤2,直到整个数组有序。2.排序的工作原理假设前i-1个元素已经有序,现在要将......
  • 选择排序.原理讲解
    背景一天，老师要李小明把10000个同学的成绩从高到底排序。李小明蒙了：“这么大，我不行呀！”正文啊，哈喽，小伙伴们大家好。我是#张亿，今天呐，学的是选择排序.原理讲解这就像我们排队是从高到矮一样，将同一类型的数据按一定顺序(从大到小或从小到大)排列称为排序。排序的算法有很多，其......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99