2019 September 09 CPP基础

C/CPP与数据结构-排序

概念

  1. 排序数学定义：假设含n个数据元素的序列为{ R1, R2, …, Rn} 其相应的关键字序列为{ K1, K2, …, Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：Kp1≤Kp2≤…≤Kpn 按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn}的操作称作排序
  2. 排序的稳定性
    1. 如果在序列中有两个数据元素r[i]和r[j]，它们的关键字k[i] == k [j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在r[j]前面，则称这个排序方法是稳定的；否则称这个排序方法是不稳定的。
  3. 多关键字排序
    1. 排序时需要比较的关键字多余一个
    2. 排序结果首先按关键字1进行排序
    3. 当关键字1相同时按关键字2进行排序
    4. 当关键字n-1相同时按关键字n进行排序
    5. 对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可！
  4. 排序中的关键操作
    1. 比较
      1. 任意两个数据元素通过比较操作确定先后次序
    2. 交换
      1. 数据元素之间需要交换才能得到预期结果
  5. 排序的审判
    1. 时间性能
      1. 关键性能差异体现在比较和交换的数量
    2. 辅助存储空间
      1. 为完成排序操作需要的额外的存储空间
      2. 必要时可以“空间换时间”
    3. 算法的实现复杂性
      1. 过于复杂的排序法会影响代码的可读性和可维护性，也可能影响排序的性能

选择法

  1. 基本思想
    1. 每一趟 (例如第 i 趟，i = 0, 1, …,n-2)在后面 n-i个待排的数据元素中选出关键字最小的元素, 作为有序元素序列的第 i 个元素。
  2. 排序过程
    1. 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换
    2. 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
    3. 重复上述操作，共进行n-1趟排序后，排序结束

  3. 代码示例：

     #include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
    
 void printArray01(int array[], int len)
 {
 	int i = 0;
 	for(i=0; i<len; i++)
 	{
 		printf("%d ", array[i]);
 	}
 	printf("\n");
 }
    
 void swap01(int array[], int i, int j)
 {
 	int temp = array[i];
 	array[i] = array[j];
 	array[j] = temp;
 }
    
 void SelectionSort(int array[], int len) // O(n*n)
 {
 	int i = 0;
 	int j = 0;
 	int k = -1;
    
 	/*
 	for (i=0; i<10; ;i++)
 	{
 		for (j=i+1; j<10; j++)
 		{
 			if (a[i] < a[j])
 			{
 				tmp = a[i];
 				a[i] = a[j];
 				a[j] = tmp;
 			}
 		}
 	}
 	*/
 	for(i=0; i<len; i++)
 	{
 		k = i; //寻找最小元素的下标
 		for(j=i+1; j<len; j++)
 		{
 			if( array[j] < array[k] ) //开始寻找最小元素的下标
 			{
 				k = j;	
 			}
 		}
    
 		//if (k != i)
 		swap01(array, i, k);
 	}
 }
    
 int main111()
 {
 	//int array[] = {12, 5, 433, 253, 216, 7};
 	int array[] = {12, 5, 433, 253};
 	int len = sizeof(array) / sizeof(*array); 
 	printArray01(array, len);
 	SelectionSort(array, len);
 	printArray01(array, len);
 	system("pause");
 	return 0;
 }

插入排序

  1. 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序
  2. 实质：对线性表执行n-1次插入操作，只是先要找到插入位置
  3. V[0], V[1], …, V[i-1]已经排好序。这时,用V[i]的关键字与V[i-1], V[i-2], …的关键字进行比较, 找到插入位置即将V[i]]插入, 原来位置上的对象向后顺移。
  4. 插入排序关键点：
    1. 拿出一个元素，留出位置
    2. 符合条件的元素后移

  5. 代码举例：

     #include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
    
 void printArray02(int array[], int len)
 {
 	int i = 0;
    
 	for(i=0; i<len; i++)
 	{
 		printf("%d ", array[i]);
 	}
    
 	printf("\n");
 }
 void InertionSort(int array[], int len) // O(n*n)
 {
 	int i = 0;
 	int j = 0;
 	int k = -1;
 	int temp = -1;
    
 	//{12, 5, 433, 253, 216, 7};
 	for(i=1; i<len; i++)
 	{
 		k = i; //待插入位置
 		temp = array[k];
    
 		for(j=i-1; (j>=0) && (array[j]>temp); j--)
 		{ 
 			array[j+1] = array[j]; //元素后移
 			k = j; //k需要插入的位置
 		}
    
 		array[k] = temp;//元素插入
 	}
 }
    
 int main222()
 {
 	int array[] = {12, 5, 433, 253, 216, 7};
 	int len = sizeof(array) / sizeof(*array); 
    
 	printArray02(array, len);
 	InertionSort(array, len);
 	printArray02(array, len);
 	system("pause");
 	return 0;
 }

冒泡排序

  1. 排序过程
    1. 将第一个记录的关键字与第二个记录的关键字进行比较，若R1>R2，则交换；然后比较第二个与第三个；依次类推，直到第n-1个和第n个比较为止
    2. 第一趟冒泡排序，结果关键字最大的会被安置在最后一个位置上
    3. 对n-1个记录进行第二趟排序，结果使关键字第二大的放在n-1位置上
    4. 重复上述过程，直到在一趟排序过程中没有进行过交换记录的操作为止。
  2. 特点：
    1. 相邻元素比较，前大则交换，否则不交换。

  3. 核心代码：

     int a[11];
 int i, j, t;
 printf("int put 10 numbers: \n");
 for ( i = 1; i < 11; i++)
 {
 	scanf("%d", &a[i]);
 	printf("\n");
 }
 for (j = 1;  j< 10; j++)
 {
 	for (i = 1; i < 10 - j; i++) {
 		if (a[i]>a[i+1])
 		{
 			t = a[i];
 			a[i] = a[i + 1];
 			a[i + 1] = t;
 		}
 	}
 }
  4. 算法优化
    1. 记住最后一次交换发生的位置lastExchange的冒泡排序，在“自上而下”冒泡排序每趟扫描中，记住最后一次交换发生的位置lastExchange，下一趟排序开始时，R[1…lastExchange-1]是有序区，[RlastExchange…n]是无序区。这样一趟排序可能使当前有序去扩充多个记录。从而减少排序的趟数。

    2. 代码示例：

       #include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
        
 void printfArray03(int array[], int len)
 {
 	int i = 0;
        
 	for(i=0; i<len; i++)
 	{
 		printf("%d ", array[i]);
 	}
 	printf("\n");
 }
        
 void swap03(int array[], int i, int j)
 {
 	int temp = array[i];
 	array[i] = array[j];
 	array[j] = temp;
 }
        
 void BubbleSort(int array[], int len) // O(n*n)
 {
 	int i = 0;
 	int j = 0;
 	//{8,3,6,1};
 	int exchange = 1; //表明数组是否已经排好序 已经排好序为0   1表示没有排好序
 	//1假设第一趟比较 已经排好序 在进行第二趟比较时候 exchange===0
 	//2 因为第一趟已经排好序,所以第2趟,没有机会执行 39
 	//3 当第3趟比较的时候 exchange==0  不满足外层循环条件,跳出外层循环..
 	for(i=0; (i<len) && exchange; i++)
 	{
 		exchange = 0;//认为已经排序完毕
 		for(j=len-1; j>i; j--)
 		{
 			if( array[j] < array[j-1] )
 			{
 				swap03(array, j, j-1);
 				exchange = 1;// 如果35 36行被执行，说明还没有排好序
 			}
 		}
 	}
 }
 int main31()
 {
 	int array[] ={8,3,6,1};
 	int len = sizeof(array) / sizeof(*array); 
 	printfArray03(array, len);
 	BubbleSort(array, len);
 	printfArray03(array, len);
 	system("pause");
 	return 0;
 }

希尔排序

  1. 排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
  2. 希尔排序是不稳定的。

  3. 代码

     #include "stdio.h"
 #include "stdlib.h"
 #include "string.h"
    
 void println(int array[], int len)
 {
 	int i = 0;
    
 	for(i=0; i<len; i++)
 	{
 		printf("%d ", array[i]);
 	}
    
 	printf("\n");
 }
 void swap(int array[], int i, int j)
 {
 	int temp = array[i];
 	array[i] = array[j];
 	array[j] = temp;
 }
    
 void InertionSort_ddddd(int array[], int len) // O(n*n)
 {
 	int i = 0;
 	int j = 0;
 	int k = -1;
 	int temp = -1;
 	//{12, 5, 433, 253, 216, 7};
 	for(i=1; i<len; i++)
 	{
 		k = i; //待插入位置
 		temp = array[k];
    
 		for(j=i-1; (j>=0) && (array[j]>temp); j--)
 		{ 
 			array[j+1] = array[j]; //元素后移
 			k = j; //k需要插入的位置
 		}
    
 		array[k] = temp;//元素插入
 	}
 }
 void ShellSort(int array[], int len) //
 {
 	int i = 0;
 	int j = 0;
 	int k = -1;
 	int temp = -1;
 	int gap = len;
 	do
 	{
 		 //业界统一实验的 平均最好情况 经过若干次后，收敛为1
 		gap = gap / 3 + 1; //gap /2345 2000 都行  //O（n 1.3） gap = 1;
    	
 		for(i=gap; i<len; i+=gap)
 		{
 			k = i;
 			temp = array[k];
    
 			for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
 			{
 				array[j+gap] = array[j];
 				k = j;
 			}
 			array[k] = temp;
 		}
 	}while( gap > 1 );
 }
    
    
 int main4111()
 {
 	int array[] = {12, 5, 433, 253, 216, 7};
 	int len = sizeof(array) / sizeof(*array); 
    
 	println(array, len);
 	ShellSort(array, len);
 	println(array, len); 
 	system("pause");
 	return 0;
 }

快速排序

  1. 思想：
    1. 快速排序是对冒泡排序的一种改进。
    2. 它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，基准数据排在这两个子序列的中间；然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

  2. 代码

     void printArray05(int array[], int len)
 {
 	int i = 0;
    
 	for(i=0; i<len; i++)
 	{
 		printf("%d ", array[i]);
 	}
    
 	printf("\n");
 }
    
 void swap5(int array[], int i, int j)
 {
 	int temp = array[i];
 	array[i] = array[j];
 	array[j] = temp;
 }
 //划分过程 第一个元素当枢轴，分成2个有效子序列
 int partition(int array[], int low, int high)
 {
 	int pv = array[low];
    
 	while( low < high )
 	{
 		while( (low < high) && (array[high] >= pv) )
 		{
 			high--; //比基准大，本来就在右边，所以high前移动
 		}
 		swap5(array, low, high);
 		while( (low < high) && (array[low] <= pv) )
 		{
 			low++;
 		}
 		swap5(array, low, high);
 	}
 	//返回枢轴的位置。。。重要
 	return low;
 }
    
    
 void QSort(int array[], int low, int high)
 {
 	if( low < high )
 	{
 		//选一个pv值，把数据分别放在pv值得左右两边，并把pivot位置返回出来。。
 		int pivot = partition(array, low, high);
    
 		//对子序列1排序
 		QSort(array, low, pivot-1);
 		//对子序列2排序
 		QSort(array, pivot+1, high);
 	}
 }
    
 void QuickSort(int array[], int len) // O(n*logn)
 {
 	QSort(array, 0, len-1);
 }
    
 int main555()
 {
 	//int array[] = {12, 5, 433, 253, 216, 7};
 	int array[] = {21,100, 3, 50, 1};
 	//int array[] = {12, 5, 433};
 	//int array[] = {12, 5};
 	int len = sizeof(array) / sizeof(*array); 
 	printArray05(array, len);
 	QuickSort(array, len);
 	printArray05(array, len);
 	system("pause");
 	return 0;
 }

归并排序（略）

All content is licensed under CC BY-NC-SA

Buit with Jekyll and 3-Jekyll theme • Hosted on Github

Table of Contents