排序算法详解-基于的固定结构以及语法

前言

本文为小书童学习的笔记，后续会进行详细的算法分析本文只是对头文件进行相应的分

头文件

#pragma once
#define DataType_s int 
/*-----------------排序算法-----------*/
//本文基于数组num[MAXSIZE]进行排序

//冒泡排序算法
//进行size-1趟比较
//每趟进行size-i-1次比较   第j位与j+1位进行比较
//每进行一趟可保证最后一位是正确的
void Sort_effe(DataType_s num[], DataType_s size)
{
	DataType_s len = size;
	DataType_s i, j;
	for (i = 0; i < len - 1; i++)//进行len-1趟
	{
		for (j = 0; j < len - 1 - i; j++)//比较len-i-1次
		{
			if (num[j] > num[j + 1])//若存在则互换值
			{
				DataType_s temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
			}
		}
	}
}

//简单选择排序算法
//找到最小的数放在第一位
void Sort_sele(DataType_s num[],DataType_s size)
{
	DataType_s i, j, temp;
	for(i=0;i<size-1;i++)     //从第一位置开始
		for (j = i + 1; j < size; j++)//第i位置与后面的数值进行比较从而获得相对最小值存储在第i位
		{
			if (num[i] > num[j])    //判断是否进行变换
			{
				temp = num[i];
				num[i] = num[j];
				num[j] = temp;
			}
		}
}

//直接插入排序算法
//将第i位之后的元素查到i之前
void Sort_inse(DataType_s num[], DataType_s size)
{
	DataType_s i;  //扫描次数
	DataType_s j;  //以j来定位比较的元素
	DataType_s temp;  //暂存数据
	for (i = 1; i < size; i++)//扫描次数为size-1
	{
		temp = num[i];
		j = i - 1; 
		while (j >= 0 && temp < num[j])   //如果未排数组比已排序数组比较最后一位小
		{
			num[j + 1] = num[j];    //把所有元素往后挪一位
			j--;
		}
		num[j + 1] = temp;
	}
}

//希尔排序法
//数据区分成特定间隔的几个小区块，以插入排序法排完区块内的数据后再渐渐减少间隔的距离。
void Sort_xier(DataType_s data[], DataType_s size)
{
	DataType_s i;	    //i为扫描次数
	DataType_s j;		//定位比较的元素
	DataType_s tmp;	//暂存数据
	DataType_s jmp;	//设置间距位移量
	jmp = size / 2;	//初始化
	while (jmp != 0)
	{
		for (i = jmp; i < size; i++)
		{
			tmp = data[i];
			j = i - jmp;
			while (tmp < data[j] && j >= 0)  //插入排序算法
			{
				data[j + jmp] = data[j];
				j = j - jmp;
			}
			data[jmp + j] = tmp;
		}
		jmp = jmp / 2;
	}
}

//归并排序算法
/*
合并排序法(MergeSort)
针对已排序好的两个或两个以上的数列(或数据文件)，
通过合并的方式将其组合成一个大的且已排好序的数列(或数据文件)
Step:
(1)将N个长度为1的键值成对地合并成N/2个长度为2的键值组。
(2)将N/2个长度为2的键值组成对地合并成N/4个长度为4的键值组。
(3)将键值组不断地合并，直到合并成一组长度为N的键值组为止
*/
void Mer(DataType_s r[],DataType_s rf[], int u, int v, int t)
{
	/*将有序的r[u--v]和r[v+1--t]归并为rf[u---t]*/
	int i, j, k;
	for (i = u, j = v + 1, k = u; i <= v && j <= t; k++)
	{
		if(r[i]<=r[j]){
			rf[k] = r[i]; i++;
		}
		else {
			rf[k] = r[j]; j++;
		}
	}
	while (i <= v) { rf[k++] = r[i++]; }
	while (j <= t) { rf[k++] = r[j++]; }  //处理剩余的数值
}


void Sort_mer(DataType_s data[], int size)
{
	DataType_s data1[30000];
	int jmp=1;
	while (jmp < size)
	{
		for (int i = 0; i < size; i++)
		{
			data1[i] = data[i];
		}
		for(int k=0;k<size-jmp;k=k+2*jmp)
		{
			Mer(data1,data, k, k + jmp-1, k + 2 * jmp - 1);
		}
		jmp = jmp * 2;
	}
}

#include<Stdio.h>
#include<time.h>
#include<stdlib.h>

int part_quick_sort(int data[], int left, int right)
{
	//单趟排序使的每次可以确定一个数据的位置
	//将区间分成按照meeti大小左右分开排序的序列
	//返回meeti即left与right相遇的地方

	int keyi = left;
	while (left < right)
	{
		while (left < right && data[right] >= data[keyi])
			right--;
		while (left < right && data[left] <= data[keyi])
			left++;
		if (left < right)//swap(data[left],data[right)
		{		
			int temp = data[left];
			data[left] = data[right];
			data[right] = temp;
		}
	}
	//swap(data[meeeti],data[keyi)
		int meeti = left;
		int temp = data[keyi];
		data[keyi] = data[meeti];
		data[meeti] = temp;
		return meeti;
}

void Quick_sort(int data[], int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = part_quick_sort(data, begin, end);
	Quick_sort(data, begin, keyi - 1);
	Quick_sort(data, keyi + 1, end);
}
void Sort_quick(int data[], int size)
{
	//快速排序入口

	Quick_sort(data, 0, size-1);
}

//堆排序
//数据存储建立为二叉树，且根结点大于（小于）子节点
//则为大根堆，小根堆
//每次输出的的时候只需输出根结点
//
//实现方式：1，建立堆->2，更新堆

//引入顺序表头文件

void Heapify(int data[], int n, int m)
{
	//维护堆的性质
	//入口参数：数组 维护结点的下标 数组长度
	int largest = n;
	int lson = n * 2 + 1;
	int rson = n * 2 + 2;
	if (lson < m && data[largest] < data[lson])
		largest = lson;
	if (rson < m && data[largest] < data[rson])
		largest = rson;
	if (largest != n)//data[n]<->data[largest]
	{
		int tem = data[largest];
		data[largest] = data[n];
		data[n] = tem;
		Heapify(data, largest, m);
	}

}
void Sort_Heap(int data[],int size)
{
	//堆排序入口函数  ->升序使用大顶堆
	//入口参数：数组  数组长度

	//建立堆
	int i;
	for (i = size / 2-1; i >=0; i--)
		Heapify(data, i, size);//建立堆时间复杂度O(n);

		for (i = size-1; i > 0; i--)
		{
			int temp = data[0];
			data[0] = data[i];
			data[i] = temp;//data[1]<->data[i]交换堆顶与堆底元素，将最大元素移到后面
			Heapify(data, 0, i - 1);//将data[1->i-1]重新调整为堆
		}
}

排序算法

前言

本文基于的固定结构以及语法

#define DataType_s int 
/*-----------------排序算法-----------*/
//本文基于数组num[MAXSIZE]进行排序

冒泡排序

作为最基本的排序算法，类似于鱼吐泡泡因此命名

//冒泡排序算法
//进行size-1趟比较
//每趟进行size-i-1次比较   第j位与j+1位进行比较
//每进行一趟可保证最后一位是正确的
void sort_effe(DataType_s num[], DataType_s size)
{
	DataType_s len = size;
	DataType_s i, j;
	for (i = 0; i < len - 1; i++)//进行len-1趟
	{
		for (j = 0; j < len - 1 - i; j++)//比较len-i-1次
		{
			if (num[j] > num[j + 1])//若存在则互换值
			{
				DataType_s temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
			}
		}
	}
}

简单选择排序

//简单选择排序算法
//找到最小的数放在第一位
void sort_sele(DataType_s num[],DataType_s size)
{
	DataType_s i, j, temp;
	for(i=0;i<size-1;i++)     //从第一位置开始
		for (j = i + 1; j < size; j++)//第i位置与后面的数值进行比较从而获得相对最小值存储在第i位
		{
			if (num[i] > num[j])    //判断是否进行变换
			{
				temp = num[i];
				num[i] = num[j];
				num[j] = temp;
			}
		}
}

直接插入排序

将未排序的元素插入到已经排序的数组中

//直接插入排序算法
//将第i位之后的元素查到i之前
void sort_inse(DataType_s num[], DataType_s size)
{
	DataType_s i;  //扫描次数
	DataType_s j;  //以j来定位比较的元素
	DataType_s temp;  //暂存数据
	for (i = 1; i < size; i++)//扫描次数为size-1
	{
		temp = num[i];
		j = i - 1; 
		while (j >= 0 && temp < num[j])   //如果未排数组比已排序数组比较最后一位小
		{
			num[j + 1] = num[j];    //把所有元素往后挪一位
			j--;
		}
		num[j + 1] = temp;
	}
}

希尔排序

希尔排序法”是D.L.Shell在1959年7月所发明的一种排序法，

可以减少插入排序法中数据搬移的次数，

以加速排序的进行

//希尔排序法
//数据区分成特定间隔的几个小区块，以插入排序法排完区块内的数据后再渐渐减少间隔的距离。
void sort_xier(DataType_s data[], DataType_s size)
{
	DataType_s i;	    //i为扫描次数
	DataType_s j;		//定位比较的元素
	DataType_s tmp;	//暂存数据
	DataType_s jmp;	//设置间距位移量
	jmp = size / 2;	//初始化
	while (jmp != 0)
	{
		for (i = jmp; i < size; i++)
		{
			tmp = data[i];
			j = i - jmp;
			while (tmp < data[j] && j >= 0)  //插入排序算法
			{
				data[j + jmp] = data[j];
				j = j - jmp;
			}
			data[jmp + j] = tmp;
		}
		jmp = jmp / 2;
	}
}

合并排序

合并排序法(MergeSort)是针对已排序好的两个或两个以上的数列(或数据文件)，通过合并的方式将其组合成一个大的且已排好序的数列(或数据文件).

步骤如下:

(1)将N个长度为1的键值成对地合并成N/2个长度为2的键值组。

(2)将N/2个长度为2的键值组成对地合并成N/4个长度为4的键值组。

(3)将键值组不断地合并，直到合并成一组长度为N的键值组为止。

合并排序法(MergeSort)
针对已排序好的两个或两个以上的数列(或数据文件)，
通过合并的方式将其组合成一个大的且已排好序的数列(或数据文件)
Step:
(1)将N个长度为1的键值成对地合并成N/2个长度为2的键值组。
(2)将N/2个长度为2的键值组成对地合并成N/4个长度为4的键值组。
(3)将键值组不断地合并，直到合并成一组长度为N的键值组为止
*/
void Mer(DataType_s r[],DataType_s rf[], int u, int v, int t)
{
	/*将有序的r[u--v]和r[v+1--t]归并为rf[u---t]*/
	int i, j, k;
	for (i = u, j = v + 1, k = u; i <= v && j <= t; k++)
	{
		if(r[i]<=r[j]){
			rf[k] = r[i]; i++;
		}
		else {
			rf[k] = r[j]; j++;
		}
	}
	while (i <= v) { rf[k++] = r[i++]; }
	while (j <= t) { rf[k++] = r[j++]; }  //处理剩余的数值
}

void sort_mer_2(DataType_s data[], int size)
{
	DataType_s data1[100];
	int jmp=1;
	while (jmp < size)
	{
		for (int i = 0; i < size; i++)
		{
			data1[i] = data[i];
		}
		for(int k=0;k<size-jmp;k=k+2*jmp)
		{
			Mer(data1,data, k, k + jmp-1, k + 2 * jmp - 1);
		}
		for (int m = 0; m < size; m++)
			printf("%d\t", data[m]);
		printf("\n");
		jmp = jmp * 2;
	}
}

快速排序算法

快速排序法又称分割交换排序法，是目前公认的最佳排序法，也是使用“分而治之”(Divideand Conquer)的方式，

会先在数据中找到一个虚拟的中间值，并按此中间值将所有打算排序的数据分为两部分。

其中小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到排序完为止