数据结构-第九章排序

墨蓝 2022-05-25 01:58 295阅读 0赞

/*
    冒泡排序的思想：不断的交换,通过交换完成最终的排序
    */

#include <iostream>
    
    using namespace std;
    void sort(int &a,int &b)
    {
    	int tmp = a;
    	a = b;
    	b = tmp;
    }
    
    void BubbleSort(int *array, int array_length)
    {
    	if (NULL == array|| 0 == array_length)
    	{
    		cout << "err NULL == array|| 0 == array_length" << endl;
    	}
    
    	for (int i = 0; i < array_length; i++)
    	{
    		for (int j = array_length - 1; j > i; j--)
    		{
    			if (array[j] < array[j-1])
    			{
    				sort(array[j] ,array[j - 1]);//较小的数字如同气泡慢慢浮到上面
    			}
    		}
    	}
    }
    //当i = 0时候,交换了1 和 2,后面已经是正常的顺序,但是用上述方法,
    //还会不依不饶的把i = 1到i =8执行一遍以及每个循环中j循环执行一遍,尽管没有发生交换数据,但是大量比较还是显得多余
    void AdvBubbleSort(int *array, int array_length)
    {
    	if (NULL == array || 0 == array_length)
    	{
    		cout << "err NULL == array|| 0 == array_length" << endl;
    	}
    	bool flag = true;
    	for (int i = 0; i < array_length && flag; i++)
    	{
    		flag = false;
    		for (int j = array_length - 1; j > i; j--)
    		{
    			if (array[j] < array[j - 1])
    			{
    				sort(array[j], array[j - 1]);//较小的数字如同气泡慢慢浮到上面
    				flag = true;//如果有数据交换,则flag为真,这样如果一次排序就完成了,后面的循环就不会需要再去执行
    			}
    		}
    	}
    }
    int main()
    {
    	int array[9] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
    	int array_length = sizeof(array) / sizeof(array[0]);
    
    	BubbleSort(array,array_length);
    
    	for (int i = 0; i < array_length; i++)
    	{
    		cout << array[i] << endl;
    	}
    
    	int array1[9] = { 2, 1,3, 4, 5, 6,7,8, 9 };
    	AdvBubbleSort(array1, array_length);
    	for (int i = 0; i < array_length; i++)
    	{
    		cout << array[i] << endl;
    	}
    	system("pause");
    	return 0;
    }

#include <iostream>
    
    using namespace std;
    /*
    简单选择排序思想:
    排序时找到合适的关键字再做交换,并且只移动一次就完成相应的关键字排序定位工作
    
    */ 
    //简单记就是：！ > 算术运算符 > 关系运算符 > && > || > 赋值运算符>逗号元素符
    void swap(int *array, int a, int b)
    {
    	array[a] = array[a] ^ array[b];
    	array[b] = array[a] ^ array[b];
    	array[a] = array[a] ^ array[b];
    }
    //简单选择排序最大特点：交换移动数据的次数相当少,这样节约了相应的时间
    //第i趟排序需要进行n-i次关键字的比较
    //简单选择排序尽管与冒泡排序同为0(n^2),但是性能上还是要略优于冒泡排序
    void SimpleSelectionSort(int *array, int  array_length)
    {
    	int min = 0;
    	for (int i = 0; i < array_length; i++)
    	{
    		min = i;
    		for (int j = i + 1; j < array_length; j++)
    		{
    			if (array[min] > array[j])//如果有小于当前最小值的关键字
    			{
    				min = j;//将此关键字的下标赋值给min
    			}
    		}
    		if (min!=i)//若min不等于i,说明找到最小值,进行交换
    		{
    			swap(array,min,i);
    		}
    	}
    
    }
    int main()
    {
    	int array[9] = {9,1,5,8,3,7,4,6,2};
    	int array_length = sizeof(array) / sizeof(array[0]);
    
    	SimpleSelectionSort(array, array_length);
    
    	for (int i = 0; i < array_length; i++)
    	{
    		cout << array[i] << endl;
    	}
    
    	system("pause");
    	return 0;
    
    }

#include <iostream>
    using namespace std;
    
    
    /**
    * 直接插入排序
    * 思想:将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表，
    * 默认将第一个元素看为有序表，一次插入后边的所欲元素
    * 时间复杂度O(n^2)
    * 空间复杂度O(1) 适用于记录数量小的
    * @param arr
    * @return
    *排序方法：程序开始运行
    此时我们传入array[6] = {0,5,3,4,6,2};length=6;
    第一趟：i=1时候,缓存待插入元素temp,	for (j = i - 1; j >= 0 && temp < arr[j]; j--)也就是for(j = 0;j>=0&&temp(5)<arr[0](0);0--)没进入循环体 直接arr[0+1]=temp,放在排序列的0后面
    第二趟：i=2时候,缓存待插入元素temp(3),	for (j = i - 1; j >= 0 && temp < arr[j]; j--)也就是for(j = 1;j>=0&&temp(3)<arr[1](5);1--)进入循环体  arr[1 + 1] = arr[1](5);向后移动,这一次循环结束j变为0,temp(3)<arr[0]错误   直接执行arr[0+1]=temp(3),放在排序列的0后面 已经排好顺序： 0  3  5
    第三趟：i=3时候,缓存待插入元素temp(4),	for (j = i - 1; j >= 0 && temp < arr[j]; j--)也就是for(j = 2;j>=0&&temp(4)<arr[2](5);2--)进入循环体  arr[2 + 1] = arr[2](5);向后移动,这一次循环结束j变为1,temp(4)<arr[1](3)错误   直接执行arr[1+1]=temp(4),放在排序列的3后面 已经排好顺序： 0  3 4 5
    第四趟：i=4时候,缓存待插入元素temp(6),	for (j = i - 1; j >= 0 && temp < arr[j]; j--)也就是for(j = 3;j>=0&&temp(6)<arr[3](5);3--)没进入循环体 直接arr[3+1]=temp(6),放在排序列的5后面  已经排好顺序： 0  3 4 5 6
    第五趟：i=5时候,缓存待插入元素temp(2),	for (j = i - 1; j >= 0 && temp < arr[j]; j--)也就是for(j = 4;j>=0&&temp(2)<arr[4](6);4--)进入循环体  arr[4 + 1] = arr[4](6);向后移动,这一次循环结束j变为3,temp(2)<arr[3](5),向后移动,这一次循环结束j变为2,temp(2)<arr[2](4),向后移动,这一次循环结束j变为1 temp(2)<arr[1](3),向后移动,这一次循环结束j变为0 temp(2)<arr[0](0)错误  直接执行arr[0+1]=temp(2),放在排序列的0后面 已经排好顺序： 0 2 3 4 5 6
    
    */
    void InsertSort(int *arr,int length) 
    {
    	//从小到大排列
    	for (int i = 1; i < length; i++)
    	{
    		//待插入元素
    		int temp = arr[i];
    		int j;
    		for (j = i - 1; j >= 0 && temp < arr[j]; j--)
    		{
    		 //待插入元素小于已有的，就将已有往后挪，直到元素大于插入元素或已经到序列最首端了 
     //待插入元素小于已有的，往后挪，直到元素大于插入元素，结束循环体，并且空出待插入位置(但是因为结束循环一次j--，故结束循环前j--，在下面待插入元素插入位置得+1才是正确插入位置)
     //待插入元素小于已有的，就将已有往后挪，直到元素大于插入元素或已经到序列最首端了,这个时候，原来首端元素后移，j--成为-1,结束循环体后，在下面带插入位置arr[-1+1]=temp即可
    			arr[j + 1] = arr[j];
    		}
    		arr[j + 1] = temp;
    	}
    }
    
    int main()
    {
    	int array[6] = {0,5,3,4,6,2};
    	int length = sizeof(array) / sizeof(array[0]);
    	InsertSort(array,length);
    
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    
    	system("pause");
    	return 0;
    }

**冒泡排序：**

思想：重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。

时间复杂度：O(n^2)

空间复杂度:O(1)

稳定性：稳定

**简单选择排序**最大的优点在于:减少了比较的次数   
(1) 无论最好最差的情况，其比较次数都是一样多的:第i趟排序需要n-i次关键字的比较，此时需要比较   
(n-1)+(n-2)+(n-3)+…+3+2+1 = n(n-1)/2;   
(2)对于交换次数而言，当最好的时候,交换次数为0，最差的时候交换次数为n-1次   
因此最终时间复杂度为:O(n2);

(3)尽管与冒泡排序同为O(n2)，但简单选择排序的性能上还是要略优于冒泡排序。

**直接插入排序**

思想：将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录增1的有序表。默认将第一个元素看为有序表，然后依次插入后边的元素

注意：这里插入元素的时候默认的策略是从后向前看，找第一个比自己小的；而不是从前向后看，找第一个比自己大的

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

希尔排序：

思想：希尔排序也是插入排序的一种，是直接针对插入排序进行改进的，该方法又称为"缩小增量排序"。

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

#include <iostream>
    using namespace std;
    /**
    * 希尔排序(缩小增量排序)
    * 希尔排序也是插入排序的一种，只是其有增量，而且最后一次增量必须为1
    * @param arr
    * @return
    */
    void ShellSort(int *array, int length)
    {
    	int step = length;
    	//保证最后一个增量为1
    	do{	
    		step = step / 3 + 1;//增量序列
    		for (int i = step; i < length; i++)
    		{
    			int temp = array[i];
    			int j = 0;
    
    			//根插入排序的区别在这里
    			for (j = i - step; j >= 0 && temp<array[j]; j -= step)
    			{
    				array[j + step] = array[j];
    			}
    			array[j + step] = temp;
    		}
    	} while (step > 1);
    }
    
    int main()
    {
    	int array[] = {12,5,433,256,216,7};
    
    	int length = sizeof(array) / sizeof(*array);
    
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    
    
    	ShellSort(array, length);
    	cout << "\n===================================分界线==========================\n";
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    
    	system("pause");
    	return 0;
    }

![70][]

![70 1][]![70 2][]

#include <iostream>
    using namespace std;
    
    
    void InsertSort(int *array, int  length)
    {
    	//从小到大
    	for (int i = 1; i < length; i++)
    	{
    		//缓存待插入元素
    		int temp = array[i];
    		int j;
    		for ( j = i - 1; j >= 0 && temp < array[j]; j--)
    		{
    			//待插入元素小于已有的,就将已有的元素往后移一位,直到插入元素大于已有元素结束循环体，
    			//并且空出待插入位置(但是因为结束循环一次j--，故结束循环前j--，在下面待插入元素插入位置得+1才是正确插入位置)
    			array[j + 1] = array[j];
    		}
    		array[j + 1] = temp;
    	}
    }
    /*
    希尔排序思想：
    就是将原本大量记录数的记录进行分组,分割成若干个子序列,此时每个子序列待排序的记录个数就比较少了,然后在这些子序列内分别进行直接插入排序
    当整个序列都基本有序时,注意只是基本有序,再对全体记录进行一次直接插入序列
    这里解释一下什么是基本有序：指的是小的关键字基本在前面,大的基本在后面,不大不小基本在中间,像{2,1,3,6,4,7,5,8,9}就可以称为基本有序
    我们分割待排序记录的目的是减少待排序的个数,使整个序列向基本有序发展，向上面所说的分完组就各自排序方法达不到我们的要求，这个时候我们需要采用
    跳跃分割的策略：将相距某个"增量"的记录组成一个子序列,这样能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
    */
    void ShellSort(int *array, int  length)
    {
    	//从小到大
    	int step = length;//缓存增量
    	do
    	{
    		step = step / 3 + 1;
    		//插入序列适当修改 把原来增量序列i改为step即可
    		for (int i = step; i < length; i++)
    		{
    			//缓存待插入元素
    			int temp = array[i];
    			int j;
    			for (j = i - step; j >= 0 && temp < array[j]; j -= step)
    			{
    				//待插入元素小于已有的,就将已有的元素往后移一位,直到插入元素大于已有元素结束循环体，
    				//并且空出待插入位置(但是因为结束循环一次j--，故结束循环前j--，在下面待插入元素插入位置得+1才是正确插入位置)
    				array[j + step] = array[j];
    			}
    			array[j + step] = temp;
    		}
    	} while (step > 1);
    
    }
    int main()
    {
    	int array[] = { 12, 5, 43, 26, 21, 7 };
    	int length = sizeof(array) / sizeof(*array);
    	//未排序前
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    	cout << "\n=========================我是分界线1================\n";
    	//直接插入排序
    	InsertSort(array,length);
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    	cout << "\n=========================我是分界线2================\n";
    
    	//希尔排序
    	ShellSort(array, length);
    	for (int i = 0; i < length; i++)
    	{
    		cout << array[i] << " ";
    	}
    	system("pause");
    	return 0;
    }

**![70 3][]**

**![70 4][]**

[70]: /images/20220525/81a61bb8d88743b3bfe4073ea11e958f.png
[70 1]: https://img-blog.csdn.net/20180507111231698?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: /images/20220525/023dbfe5c7134337bdbb9f02dfb346b3.png
[70 3]: /images/20220525/2ad00fa78b2146218e10f3a15a281fe9.png
[70 4]: /images/20220525/b9f7bc3fe68542709b499e988aa4bef5.png