常见基本排序算法

不念不忘少年蓝@ 2022-10-08 14:21 196阅读 0赞

### 文章目录 ###

*  直接插入排序
 *  希尔排序
 *  归并排序
 *  快速排序
 *  应用

# 直接插入排序 #

一个一个逐步插入  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]

//直接插入排序
    void InsertSort(SqList& L)
    {
        
    	int i, j;
    	for (i = 2; i <= L.length; i++)
    	{
        
    		InsertSortCount++;
    		if (L.r[i].key < L.r[i - 1].key) //小于时,将R[i]插入有序表
    		{
        
    
    			L.r[0] = L.r[i]; // R[0]作监测哨兵
    			L.r[i] = L.r[i - 1];
    			for (j = i - 2; L.r[0].key < L.r[j].key; j--) {
        
    				InsertSortCount++;
    				L.r[j + 1] = L.r[j]; //记录后移
    			}
    			L.r[j + 1] = L.r[0]; //插入到正确位置
    		}
    	}
    }

# 希尔排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]

//希尔排序
    void ShellInsert(SqList& L,int dk) //步长为dk的插入排序
    {
        
    	int i, j;
    	for (i = dk + 1; i <= L.length; i++) {
        
    		
    		ShellSortCount++;
    		if (L.r[i].key < L.r[i - dk].key) //小于时,需将r[i]插入有序表
    		{
        
    			
    			L.r[0] = L.r[i]; //为统一算法设置监视哨
    			for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) {
        
    				L.r[j + dk] = L.r[j]; //记录后移				
    			}
    			L.r[j + dk] = L.r[0]; //插入到正确位置
    		}
    	}
    }
    void ShellSort(SqList& L,int dita[],int t)
    {
         //按增量序列dlta[0,1…,t-1]对顺序表S作希尔排序
    	for (int k = 0;k < t;k++)
    		ShellInsert(L,dita[k]);
    }

# 归并排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]

//归并排序算法
    void Merge(RedType SR[], RedType TR[], int i, int m, int n)
    {
        
    	int j, k;
    	for (j = m + 1, k = i; i <= m && j <= n; k++) {
        
    		MergeSortCount++;
    		if (SR[i].key <= SR[j].key) TR[k] = SR[i++];
    		else TR[k] = SR[j++];
    	}
    	while (i <= m) TR[k++] = SR[i++];
    	while (j <= n) TR[k++] = SR[j++];
    }
    void Msort(RedType p1[], RedType p2[], int n, int l)
    {
        
    	int i = 1, j;
    	while (i + 2 * l - 1 <= n)
    	{
        
    		Merge(p1, p2, i, i + l - 1, i + 2 * l - 1);
    		i = i + 2 * l;
    	}
    	if (i + l <= n) Merge(p1, p2, i, i + l - 1, n);
    	else for (j = i; j <= n; j++) p2[j] = p1[j];
    }
    void MergeSort(SqList& L)
    {
        
    	int l = 1;
    	RedType s[101];
    	while (l < 100)
    	{
        
    		Msort(L.r, s, L.length, l);
    		l = l * 2;
    		Msort(s, L.r, L.length, l);
    		l = l * 2;
    	}
    }

# 快速排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]

//快速排序
    int Partition(SqList& L, int low, int high)
    {
        
    	L.r[0] = L.r[low]; //以子表的第一个记录作为轴值记录
    	int pivotkey = L.r[low].key; //取轴值记录关键字
    	while (low < high) //从表的两端交替地向中间扫描
    	{
        
    		QSortCount++;
    		while (low < high && L.r[high].key >= pivotkey) high--;
    		if (low < high) L.r[low++] = L.r[high];
    		//将比轴值记录小的交换到低端
    		while (low < high && L.r[low].key <= pivotkey) low++;
    		if (low < high) L.r[high--] = L.r[low];
    	} //将比轴值记录大的交换到高端
    	L.r[low] = L.r[0]; //轴值（支点）记录到位
    	return low; //返回轴值（支点）记录所在位置
    }
    void QSort(SqList& L, int low, int high)
    {
         //对顺序表L中的子序列L.r[low…high]作快速排序
    	if (low < high)
    	{
        
    		int pivotloc = Partition(L, low, high);
    		QSort(L, low, pivotloc - 1); //对小于轴值序列实现递归排序
    		QSort(L, pivotloc + 1, high);
    	} //对大于轴值序列实现递归排序
    }

# 应用 #

例题：  
随机产生100 个整数构成的序列,  
分别以直接插入、希尔、快速、归并等排序算法排序,  
并统计各自的比较次数

/*
    3、随机产生100 个整数构成的序列,
    分别以直接插入、希尔、快速、归并等排序算法排序,
    并统计各自的比较次数
    */
    #include <iostream>
    using namespace std;
    
    typedef int KeyType;
    typedef int InfoType;
    
    # define Maxsize 200 //待排序序列中记录的最大个数
    # define T 7
    
    int InsertSortCount = 0, ShellSortCount = 0, QSortCount = 0, MergeSortCount = 0;
    
    
    // 待排序表中每个数据元素的数据类型定义
    typedef struct
    {
        
    	KeyType key; //表示排序关键字
    	//InfoType otherinfo; //排序记录中的其他所有数据项
    } RedType;
    // 待排序数据表的数据类型定义
    typedef struct
    {
        
    	RedType r[Maxsize + 1]; //存放待排序全体记录
    	int length; //排序记录个数
    } SqList;
    
    //直接插入排序
    void InsertSort(SqList& L)
    {
        
    	int i, j;
    	for (i = 2; i <= L.length; i++)
    	{
        
    		InsertSortCount++;
    		if (L.r[i].key < L.r[i - 1].key) //小于时,将R[i]插入有序表
    		{
        
    
    			L.r[0] = L.r[i]; // R[0]作监测哨兵
    			L.r[i] = L.r[i - 1];
    			for (j = i - 2; L.r[0].key < L.r[j].key; j--) {
        
    				InsertSortCount++;
    				L.r[j + 1] = L.r[j]; //记录后移
    			}
    			L.r[j + 1] = L.r[0]; //插入到正确位置
    		}
    	}
    }
    //希尔排序
    void ShellInsert(SqList& L,int dk) //步长为dk的插入排序
    {
        
    	int i, j;
    	for (i = dk + 1; i <= L.length; i++) {
        
    		
    		ShellSortCount++;
    		if (L.r[i].key < L.r[i - dk].key) //小于时,需将r[i]插入有序表
    		{
        
    			
    			L.r[0] = L.r[i]; //为统一算法设置监视哨
    			for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk) {
        
    				L.r[j + dk] = L.r[j]; //记录后移				
    			}
    			L.r[j + dk] = L.r[0]; //插入到正确位置
    		}
    	}
    }
    void ShellSort(SqList& L,int dita[],int t)
    {
         //按增量序列dlta[0,1…,t-1]对顺序表S作希尔排序
    	for (int k = 0;k < t;k++)
    		ShellInsert(L,dita[k]);
    }
    //快速排序
    int Partition(SqList& L, int low, int high)
    {
        
    	L.r[0] = L.r[low]; //以子表的第一个记录作为轴值记录
    	int pivotkey = L.r[low].key; //取轴值记录关键字
    	while (low < high) //从表的两端交替地向中间扫描
    	{
        
    		QSortCount++;
    		while (low < high && L.r[high].key >= pivotkey) high--;
    		if (low < high) L.r[low++] = L.r[high];
    		//将比轴值记录小的交换到低端
    		while (low < high && L.r[low].key <= pivotkey) low++;
    		if (low < high) L.r[high--] = L.r[low];
    	} //将比轴值记录大的交换到高端
    	L.r[low] = L.r[0]; //轴值（支点）记录到位
    	return low; //返回轴值（支点）记录所在位置
    }
    void QSort(SqList& L, int low, int high)
    {
         //对顺序表L中的子序列L.r[low…high]作快速排序
    	if (low < high)
    	{
        
    		int pivotloc = Partition(L, low, high);
    		QSort(L, low, pivotloc - 1); //对小于轴值序列实现递归排序
    		QSort(L, pivotloc + 1, high);
    	} //对大于轴值序列实现递归排序
    }
    //归并排序算法
    void Merge(RedType SR[], RedType TR[], int i, int m, int n)
    {
        
    	int j, k;
    	for (j = m + 1, k = i; i <= m && j <= n; k++) {
        
    		MergeSortCount++;
    		if (SR[i].key <= SR[j].key) TR[k] = SR[i++];
    		else TR[k] = SR[j++];
    	}
    	while (i <= m) TR[k++] = SR[i++];
    	while (j <= n) TR[k++] = SR[j++];
    }
    void Msort(RedType p1[], RedType p2[], int n, int l)
    {
        
    	int i = 1, j;
    	while (i + 2 * l - 1 <= n)
    	{
        
    		Merge(p1, p2, i, i + l - 1, i + 2 * l - 1);
    		i = i + 2 * l;
    	}
    	if (i + l <= n) Merge(p1, p2, i, i + l - 1, n);
    	else for (j = i; j <= n; j++) p2[j] = p1[j];
    }
    void MergeSort(SqList& L)
    {
        
    	int l = 1;
    	RedType s[101];
    	while (l < 100)
    	{
        
    		Msort(L.r, s, L.length, l);
    		l = l * 2;
    		Msort(s, L.r, L.length, l);
    		l = l * 2;
    	}
    }
    void display(SqList L) {
        
    	for (int i = 1; i <= 100; i++) {
        
    		cout << L.r[i].key << "\t";
    		if (i % 10 == 0) {
        
    			cout << endl;
    		}
    	}
    }
    int main() {
        
    
    	//int a[800];
    
    	///*
    	//rand() % n +a;
     //其中的a是起始值，n-1+a是终止值，n是整数的范围
    	//*/
    	//for (int i = 0; i < 100; i++) {
        
    	//	a[i] = rand() % 200 + 1;
    	//}
    
    	SqList L;
    	L.length = 100;
    	for (int i = 1; i <= 100; i++) {
        
    		L.r[i].key = rand() % 200 + 1;
    	}
    
    	cout << "随机生成的100个数：" << endl;
    	display(L);
    
    	int dita[T] = {
         49,37,29,23,19,11,1 };
    	int c = 1;
    	
    	while (c)
    	{
        
    		cout << "+=====================================+" << endl;
    		cout << "|             1.直接插入排序          |" << endl;
    		cout << "|             2.希尔                  |"<< endl;
    		cout << "|             3.快速                  |"<< endl;
    		cout << "|             4.归并                  |" << endl;
    		cout << "|             0.退出                  |" << endl;
    		cout << "+=====================================+" << endl;
    		cout << "请选择：";
    		cin >> c;
    		switch (c)
    		{
        
    		case 1:
    			cout << endl << "直接插入排序：" << endl;
    			InsertSort(L);
    			display(L);
    			cout << "比较次数：" << InsertSortCount << endl;
    			cout << endl;
    			break;
    		case 2:
    			cout << endl << "希尔:" << endl;
    			ShellSort(L, dita, T);
    			display(L);
    			cout << "比较次数：" << ShellSortCount << endl;
    			cout << endl;
    			break;
    		case 3:
    			cout << endl << "快速:" << endl;
    			QSort(L, 0, 100);
    			display(L);
    			cout << "比较次数：" << QSortCount << endl;
    			cout << endl;
    			break;
    		case 4:
    			cout << endl << "归并:" << endl;
    			MergeSort(L);
    			display(L);
    			cout << "比较次数：" << MergeSortCount << endl;
    			cout << endl;
    			break;
    		default:
    			break;
    		}
    	}
    
    
    
    	
    	//int dita[10];
    	//int t = 10;
    	//for (int i = 0; i < t; i++) {
        
    	//	if (i == 0) {
        
    	//		dita[0] = 49;
    	//	}
    	//	else {
        
    	//		dita[i] = dita[i - 1] / 2 + 1;
    	//		if (dita[i] <= 1) {
        
    	//			dita[i] = 1;
    	//		}
    	//	}
    	//}
    	
    
    	
    
    	
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: /images/20221005/9e4e75d3fa6d4b6abd4f06ca6a74ee34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 1]: /images/20221005/2a0ec67af08f4efbbf2859406453ebc1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 2]: /images/20221005/70a17fb57a414bcabefcb033f3e5cc81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70 3]: /images/20221005/c6e5d4b59821439888a9603ed6d77aa8.png