数据结构基本排序（c语言）_结构体排序c语言

        在初步学完初阶数据结构的排序后，我发现了一个非常不得了的问题。那就是，在拿出一个排序的名字时（除了几个令人印象深刻的），我根本不能第一时间想起它们的思路啊！！！这就好比上厕所时，感觉要出来但又出不来一样令人难以接受。于是我准备写一篇博客来总结一下。

目录

1.冒泡排序

（1）思路

（2）代码实现 

2.插入排序

（1）思路

(2)下面来举个栗子。 

(3)代码实现

 3.希尔排序

（1）思路

代码优化（实现）：

4.直接选择排序

思路：

代码实现：

5.堆排序

思路：

 画图举例：

代码实现：

6.快速排序

1，hoare版本

三数取中：（选取数组最左边数，最右边数，中间的数。三者中第二大的数）

2，挖坑法

 3，前后指针法

 快速排序主体（递归实现）

7.归并排序

思路（图解）：

代码实现：

---

1.冒泡排序

        首先就是我们的老伙计了，相比较其他排序老伙计算是较容易实现的了。

（1）思路

        

思路： 从初始位置开始进行比较，也就是将arr[0]与arr[1]进行比较。如果arr[0]大于arr[1]，则将两者值进行交换。然后将arr[1]与arr[2]进行比较........依此类推。每次比较完一轮后，就代表比较后最大的值到达了正确的位置，这时只需要将下轮要比较的总个数-1就行了。

（2）代码实现 

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 0;
		for (int j = 1; j < n - i; j++)//i的逐步增加实现了下轮比较总个数的减少
		{
			if (arr[j-1] > arr[j])
			{
				swap(&arr[j - 1], &arr[j]);
				flag = 1;
			}
		}
		if (0 == flag)//当比较完一轮后，flag==0，则说明数据已经有序了
			break;
	}
}

2.插入排序

（1）思路

 思路：插入排序就像打扑克摸牌一样，摸完一张牌后，就把它插到比它小的牌和比它大的牌中间。

也就是说，假设[0,end]区间内数据是有序的，接下来插入end+1位置的数。

令tmp = arr[end+1]。然后从arr[end]开始到arr[0]依次与tmp进行比较。(即end--，直到end<0或者.新入数据已插入，为止)。

如果tmp小，则将与tmp进行比较的数据向后“移”。

如果tmp大，则arr[end+1] = tmp。 

(2)下面来举个栗子。 

arr[end]与tmp比较，5>3,所以5向后移。end--.

 

 同理4后移

 

直到2<3,tmp插入，即arr[ end+1] = tmp.

(3)代码实现

//插入排序
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;
	}
}

 3.希尔排序

        希尔排序与插入排序思路是一样的，只是希尔排序在插排的基础上加了一层优化。(预排序）

        预排序的目的呢，当然就是使数据接近有序啦。

（1）思路

        那，预排序到底是什么东东呢。

其实就是将间隔为gap的数据分为一组，然后进行插入排序。

 如此，较大的数据就会更快地到后面，较小的数据就会更快地到前面。

代码实现：只需要在插入排序的基础之上稍加改动就行了。

void ShellSort(int* arr, int n)
{
	for (int gap = 3; gap > 0; gap--)
	{
		for (int j = 0; j < gap; ++j)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = arr[end + gap];
				while (end >= 0)
				{
					if (arr[end] > tmp)
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				arr[end + gap] = tmp;
			}
		}
	}
}

 但，看着上面的代码感觉循环太多了，令人很不爽。于是就有了下面的优化。

代码优化（实现）：

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while(gap > 1)
	{
		gap = gap / 3 + 1;//使gap最终变为1
		for (int i = 0; i < n - gap; i++)//gap组数据依次多组并排 
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

 优化思路

排完红色一组的第一个数据后，i++，去排绿组的第一个数据，再i++，去排蓝组的第一个数据，再i++，去排红组第二个数据.........

4.直接选择排序

思路：

 其实就是将数据一个一个一个地比较，选出最小的数据，放在最左边。既然，都选出了最小的，为什么我们不再选一个最大的放在最右边呢。这么一来，新的优化思路就出现啦！

 代码实现（有bug)：

void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//选出小的放begin
		//选出大的放end
		int max = begin, min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}
		swap(&arr[begin], &arr[min]);
		swap(&arr[end], &arr[max]);
		++begin;
		--end;
	}
}

上面的代码虽然已经差不多实现出来了，但是还有一个非常容易忽略的坑。就是

当最大值正好在最左侧，min与最左侧值交换后，min就变成了所谓的“最大”。导致排序出错。这个坑只会在同时选max,min时出现，也就是在优化的思路中出现，如果只是简单地选出min放左边并不会受到影响。

 所以就需要对max进行修正。

代码实现：

//选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//选出小的放begin
		//选出大的放end
		int max = begin, min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;
			}
			if (arr[i] > arr[max])
			{
				max = i;
			}
		}
		swap(&arr[begin], &arr[min]);
		//修正max
		if (max == begin)
			max = min;
		swap(&arr[end], &arr[max]);
		++begin;
		--end;
	}
}

5.堆排序

        堆排序与其他的排序还是有很大不同的，并且如果要理解堆排序，最最重要的方法就是画图啦。如果不画图，那就相当于把刀扔在旁边，直接用空手去劈榴莲。为了方便手不铁的我，所以接下来我就多用画图来解释了。

思路：

        思路：刚开始的数据是无序的，所以就需要将它们建成大堆或者小堆（以下使用大堆）

                   我们可以把父节点与子节点比较，确保最大的数位于父节点位置。

向下调整函数： 

//向下调整（确保最大的数位于父节点位置）
void Adjustdown(Type* arr, int sz, int parent)
{
	int minchild = parent * 2 + 1;//初始为左孩子
	while (minchild < sz)
	{
		//取左右孩子中最大的
		if (arr[minchild] < arr[minchild + 1] && minchild + 1 < sz)
		{
			minchild++;//变为右孩子
		}
		if (arr[minchild] > arr[parent])
		{
			swap(&arr[parent], &arr[minchild]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

 因为叶子节点本身就是一个天然的堆，所以，只需要从倒数第一个非叶子节点（最后一个节点的父亲）开始调整。

//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//倒数第一个非叶子节点（最后一个节点的父亲）开始调整
	{										  //由child = parent*2+1  推出parent = （child-1）/2   即  （n-1 -1)/2
		Adjustdown(arr, n, i);
	}

以下一组数据{9，1，2，4，8，6，7，5，3}为例。 

（1）i = (n-1 -1)/2 = 3,所以将arr[3]与子节点比较，即4与5，3比较。因为5>4，所以4与5交换位置。

（2）i--, 所以将arr[2]与子节点比较，即2与6，7比较。因为7>6>2，所以2与7交换位置。

（3）同理，得到以下结果。

 

这么一来，大堆就建好啦。

然后是选数，将根节点位置的数与最后的叶子节点交换，再进行向下调整，确保根节点位置数在剩下的数中最大，最后size--,让最后一个排好的数不进入之后的排序。每次交换使得最大的数到达正确的位置，如此反复，堆排序就完成啦！ 

//选数
	int i = 1;
	while (i < n)
	{
		swap(&arr[0], &arr[n - i]);//每次交换使得最大的数到达正确的位置
		Adjustdown(arr, n - i, 0);
		i++;
	}

 画图举例：

交换根节点位置的数与最后叶子节点位置的数

向下调整

 

 交换根节点位置的数与最后叶子节点位置的数

向下调整

 

  交换根节点位置的数与最后叶子节点位置的数

向下调整

 

依此类推

 最终实现堆排序

代码实现：

//堆排序
void Heap_sort(int* arr, int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//倒数第一个非叶子节点（最后一个节点的父亲）开始调整
	{										  //由child = parent*2+1  推出parent = （child-1）/2   即  （n-1 -1)/2
		Adjustdown(arr, n, i);
	}
	//选数
	int i = 1;
	while (i < n)
	{
		swap(&arr[0], &arr[n - i]);//每次交换使得最大的数到达正确的位置
		Adjustdown(arr, n - i, 0);
		i++;
	}
}

6.快速排序

        从名字可以看出来，快速排序的主要特点就是，快！

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，之后又有一些大佬对其进行了优化，还有一些大佬又用别的思路将它实现了。所以，接下来有三种不同版本的快排实现思路。（啊啊啊，写死我啦）

1，hoare版本

思路：

 总的来说就是，R找比key小的数，找到之后，R不动。L开始行动找比key大的数，找到后，交换两数位置,R继续行动......两者相遇后将相遇位置的值与key交换。如此，6左边全是比6小的数，右边全是比6大的数。（以图中为例）即，6到达最终的位置。再用递归来实现快排（在最后快排主体）。

因为考虑到代码效率的问题，key使用三数取中的方法来选取的效率，比直接key=arr[0]的效率高。所以，下面我就使用三数取中了哦。 

三数取中：（选取数组最左边数，最右边数，中间的数。三者中第二大的数）

//三数取中
int GetMidIndex(int* arr, int left, int right)
{
	int mid = (right + left) / 2;
	if (arr[mid] > arr[left])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[left] < arr[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

代码实现：

//快速排序hoare版本[left,right]
int PartSort1(int* arr, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(arr, left, right);
	swap(&arr[mid], &arr[left]);
	int keyi = left;
	while (left < right)
	{
		//R找小
		while (left < right && arr[right] >= arr[keyi])//因为right在变化，所以要时时刻刻判断left<right
		{
			--right;
		}
		//L找大
		while (left < right && arr[left] <= arr[keyi])//因为left在变化，所以要时时刻刻判断left<right
		{
			++left;
		}
		if (left < right)
			swap(&arr[left], &arr[right]);
	}
	swap(&arr[left], &arr[keyi]);
	//返回相遇点
	return left;
}

2，挖坑法

思路：

挖坑法的思路与 hoare版本是相似的，R找比key大的数，填到左边的坑，形成新的坑位，然后L行动，找比key小的数，填到右边的坑，形成新坑位......两者相遇后，把key填入相遇点。

代码实现：

int PartSort2(int* arr, int left, int right)
{
	// 三数取中
	int mid = GetMidIndex(arr, left, right);
	swap(&arr[left], &arr[mid]);
 
	int key = arr[left];
	int hole = left;
	while (left<right)
	{
		//右边找大，填左坑
		while (left < right && arr[right] >= key)//因为right在变化，所以要时时刻刻判断left<right
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;
		//左边找小，填右坑
		while (left < right && arr[left] <= key)因为left在变化，所以要时时刻刻判断left<right
		{
			++left;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	//返回相遇点
	return hole;
}

 3，前后指针法

思路：

 初始时，prev指针指向序列开头，cur指针指向prev指针的后一个位置。

然后判断cur指针指向的数是否小于key，若小于，则prev指针后移一位，cur指向的内容与prev指向的内容交换（prev与cur在同一位置时不变），然后cur++。若大于，直接cur++。

当cur越界时将prev指向内容与key进行交换。

 代码实现：

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int mid = GetMidIndex(a, left, right);
	swap(&a[left], &a[mid]);
 
	int key = a[left];
	int prev = left;
	int cur = left + 1;
	//cur找小，prev紧跟
	while (prev <= cur)
	{
		//cur甩开prev后，并遇到小时交换
		if (a[cur] < key && ++prev != cur)
		{
			swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	swap(&a[left], a[prev]);
	return prev;
}

 快速排序主体（递归实现）

思路：

首先对初始数组排序使6到达最终位置，再对6的左边数组进行排序使3到达最终位置，再对6右边数组进行排序使8到达最终位置。再对3左边数组.........最终实现有序。（二叉树结构）

//快速排序[begin,end]
void QuickSort(int* arr, int begin, int end)
{
	//为空或只有一个时返回
	if (begin >= end)
		return;
	if (end - begin <= 8)
	{
		insertSort(arr + begin, end - begin + 1);//当数组较小时，使用插入排序，提高效率
	}
	else
	{
		int keyi = PartSort1(arr, begin, end);//以上三种方法任选一个
		//左
		QuickSort(arr, begin, keyi - 1);
		//右
		QuickSort(arr, keyi + 1, end);
	}
}

7.归并排序

思路（图解）：

代码实现：

//归并排序
void mergeSort(int* arr, int begin, int end, int* tmp)
{
	//分解
	//数组中数据个数为1或者0时返回
	if (begin >= end)
		return;
 
	int mid = (begin + end) / 2;
 
	//左
	mergeSort(arr, begin, mid, tmp);
	//右
	mergeSort(arr, mid + 1, end, tmp);
	
	//合并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	//将小的放入tmp数组
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
			tmp[i++] = arr[begin1++];
		else
			tmp[i++] = arr[begin2++];
	}
 
	//将大的尾插到tmp数组
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
 
	//将tmp拷贝回原来数组
	memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
 
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc");
		return;
	}
 
	mergeSort(arr, 0, n - 1, tmp);
 
	free(tmp);
	tmp = NULL;
}
 

 啊！！！终于写完啦，最后写地脑壳疼·，如果大家发现了我哪里写错了欢迎斧正哦！文中动图来源于网络。

欧拉欧拉欧拉欧拉欧拉欧拉欧拉欧拉欧拉欧拉！！！！！

木大木大木大木大木大木大木大木大木大木大！！！！！