数据结构与算法排序_数据结构与算法排序

作者：从前慢现在也慢 | 2024-04-30 04:25:32

踩

数据结构与算法排序

一、简述

记-排序方法。冒泡排序、选择排序、快速排序、直接插入排序。

排序方法优劣比较：

注：排序稳定性：如果待排序的表中存在多个关键字相同的元素，经过排序后这些相同关键字的元素的相对次序保持不变，则称这种排序方法是稳定的。反之有可能发生变化的则为不稳定。（例如按年龄排序，A与B的年龄相同，排序前A在B的前面，排序后A一定在B的前面，如此称为稳定。）

二、冒泡排序

例如有N个数需要排序，第1趟比较N个数，相邻的两个数进行比较，较大值者后移(从小到大排序)，一趟比较结束后，这一趟比较的数当中的最大值成为最后一个数；第2趟比较剩下的N-1个数，其中的最大值成为第N-1个数；以此类推，一共比较N-1趟。

测试代码：


#include <stdio.h>
 
#define LENGTH	10	//元素个数
 
void bubble_sort(int arr[], int len)
{
	int i, j, tmp, print; 
 	for (i = 0; i < len; i++)			/*变量i代表比较的趟数，每趟将未排序中的最大值放到最后*/
    {
    	for (j = 0; j < len-1-i; j++)	/*变量j代表每趟两两比较的次数*/
    	{
    		if (arr[j] > arr[j+1])        /*比较相邻的两值，大者后移*/   
		    {
		        tmp = arr[j];				/*利用中间变量实现两个值互换*/
		        arr[j] = arr[j+1];
		        arr[j+1] = tmp;
		    }
		} 
		
	 	printf("第%d趟比较后：", i);
	    for (print = 0; print < LENGTH; print++)
	    {
	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
		} 
		printf("\n"); 
		 
	} 
} 
 
int main()
{
    int i, arr[10];					/*定义变量及数组*/
    printf("请输入10个数:\n");
    for (i = 0; i < 10; i++)
    {
    	scanf("%d", &arr[i]);				/*从键盘中输入10个数*/
	}
   
    bubble_sort(arr, LENGTH);
	 
    printf("排序后的顺序是:\n");
    for (i = 0; i < 10; i++)
    {
    	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
	} 
	printf("\n");
	return 0;
}

运行结果：

改进：有时候比较了前几次就排好序了(某一趟比较中没有发生交换，即没有反序，说明已经是顺序的)，就不用继续比较，以节约资源。

测试代码：


#include <stdio.h>
 
#define LENGTH	10	//元素个数
 
void bubble_sort(int arr[], int len)
{
	int i, j, tmp, print,is_exchange; 
 	for (i = 0; i < len; i++)			/*变量i代表比较的趟数，每趟将未排序中的最大值放到最后*/
    {
    	is_exchange = 0; 
    	for (j = 0; j < len-1-i; j++)	/*变量j代表每趟两两比较的次数*/
    	{
    		if (arr[j] > arr[j+1])        /*比较相邻的两值，大者后移*/   
		    {
		        tmp = arr[j];				/*利用中间变量实现两个值互换*/
		        arr[j] = arr[j+1];
		        arr[j+1] = tmp;
		        is_exchange = 1; //标志为发生交换 
		    }
		} 
		
	 	printf("第%d趟比较后：", i);
	    for (print = 0; print < LENGTH; print++)
	    {
	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
		} 
		printf("\n"); 
		
		if(is_exchange == 0)//没有发生交换，说明已经是排好序的 
		{
			return; 
		} 
		 
	} 
} 
 
int main()
{
    int i, arr[10];					/*定义变量及数组*/
    printf("请输入10个数:\n");
    for (i = 0; i < 10; i++)
    {
    	scanf("%d", &arr[i]);				/*从键盘中输入10个数*/
	}
   
    bubble_sort(arr, LENGTH);
	 
    printf("排序后的顺序是:\n");
    for (i = 0; i < 10; i++)
    {
    	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
	} 
	printf("\n");
	return 0;
}

运行结果：

三、直接选择排序

例如有N个数，第1趟从待排序的N数当中选出最小值最为第1个数，第2趟从剩下未排序的N-1个数中选出最小值最为第2个数，以此类推，直到全部将N个数排序。

测试代码：


#include <stdio.h>
#define LENGTH	10	//定义数组元素个数 
 
void select_sort(int arr[], int len)//选择排序 
{
	int i, j, k, tmp, print;
	for (i = 0; i < len-1; i++)			/*变量i代表比较的趟数，每趟将未排序中的最小值放到前面*/
    {
    	k = i;//k用来记住每趟中最小值元素的数组索引，比较完一趟再进行交换 
    	for (j = i+1; j < len; j++)	/*变量j代表每趟两两比较的次数*/
    	{
    		if (arr[j] < arr[k])    /*大者后移*/   
		    {
		    	k = j; 
		    }
		} 
		
		if (k != i)   /*将无序区的最小值放到有序区*/   
	    {
	        tmp = arr[i];				/*利用中间变量实现两个值互换*/
	        arr[i] = arr[k];
	        arr[k] = tmp;
	    }
	    
	    printf("第%d趟比较后：", i);
	    for (print = 0; print < LENGTH; print++)
	    {
	    	printf("%d ", arr[print]);            /*将排序后的顺序输出*/
		} 
		printf("\n"); 
	} 
}
 
int main()
{
    int i, arr[LENGTH];   
    printf("请输入%d个数:\n", LENGTH);
    for (i = 0; i < LENGTH; i++)
    {
    	scanf("%d", &arr[i]);				/*从键盘中输入LENGTH个数*/
	}
	
	select_sort(arr, LENGTH); 
    
    printf("排序后的顺序是:\n");
    for (i = 0; i < LENGTH; i++)
    {
    	printf("%d ", arr[i]);            /*将排序后的顺序输出*/
	} 
	
	printf("\n");
	return 0;
}

运行结果：

四、快速排序

快速排序是由冒泡排序改进而来的。

一趟快速排序的划分过程是采用从两头向中间扫描，同时交换与基准元素逆序的元素。具体做法是：设两个标识i和j，它们初始化分别指向无序区中的第一个元素和最后一个元素。假设无序区中的元素为arr[begin],arr[begin+1],...,arr[end]。则i的初始值为begin，j的初始值为end；首先将arr[begin]的值赋给中间变量tmp作为基准，然后令j自end起向左(向begin方向)扫描，直至arr[j]<tmp,然后将arr[j]的值赋给arr[i]。然后令i自i+1向右(向end方向)扫描，直至arr[i]>tmp,然后将arr[i]的值赋给arr[j]。然后令j自j-1向右..;然后令i自i+1向右。。。这样重复操作直到i==j，此时arr[begin],arr[begin+1],...,arr[i-1]这些关键字都小于tmp，而所有的.arr[i+1],...,arr[end]的关键字都大于tmp，此时可以将tmp中的元素赋给arr[i]。

测试代码


#include <stdio.h>
 
static int index = 0;
 
void Print(int arr[],int len)
{
	int i;
	for(i=0;i<len;++i)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}
 
void quick_sort(int arr[],int begin,int end)//将arr[begin]...arr[end]进行快速排序 
{
	int i = begin,j = end;
	int tmp;
	if(begin<end)
	{
		tmp = arr[begin];//取arr[begin]作为基准 
		while(i!=j)//从两端向中间扫描，直至i==j 
		{
			while(j>i && arr[j] >= tmp)//从右向左扫描，找到第一个小于tmp的arr[j] 
			{
				--j;
			}
			
			arr[i] = arr[j];//找到第一个小于tmp的arr[j]，将arr[j]赋给arr[i] 
			
			while(i<j && arr[i] <= tmp)//从左向右扫描，找到第一个大于tmp的arr[i]
			{
				++i;
			}
			arr[j] = arr[i];//找到第一个大于tmp的arr[i]，将arr[i]赋给arr[j] 
		}
		
		arr[i] = tmp;//arr[i]归位 
		printf("第%d趟：", index++);
		Print(arr, 10);//打印当前排序后的元素 
		
		quick_sort(arr,begin,i-1);//对左区间进行递归快速排序 
		quick_sort(arr,i+1,end);//对右区间进行递归快速排序
	}
}
 
int main(int argc,char* argv[])
{
	int arr[] = {6, 8, 7, 9, 0, 1, 3, 2, 4, 5};
	printf("before sort:");
	Print(arr, sizeof(arr)/sizeof(arr[0]));
	quick_sort(arr,0,sizeof(arr)/sizeof(arr[0] - 1));
	printf("after  sort:");
	Print(arr, sizeof(arr)/sizeof(arr[0]));
	return 0;
}

运行结果：

五、直接插入排序（稳定）

基本思想：把n个待排序的元素看为有序区和无序区，开始时有序区中只包含1个元素，无序区中包含有n-1个元素，排序过程中每次从无序区中取出第一个元素，将它插入到有序区中的适当位置；直到将无序区的元素都取完，排序完成。

图例：

测试代码：


#include <stdio.h>
 
void print_arr(int arr[], int len)//打印数组arr,len为数组的个数 
{
	int i;
	printf("arr= ");
	for(i=0; i<len; i++)
	{
		printf("%-3d ", arr[i]);
	}
	printf("\n");
} 
 
//直接插入排序，arr为待排序的数组，len为数组的长度 
void straight_insertion_sort(int arr[], int len)
{
	//进行从小到大排序 
	int i,j,save;
    for(i=1;i<len;i++)//第一个元素作为有序区第一个元素，从第二个元素开始，逐个插入有序区 
    {
        if(arr[i]<arr[i-1])//当前要插入的元素比前面的元素要小，前面的元素往后移，腾挪出一个位置，放置当前要插入的数 
        {
            save = arr[i];//因为要进行移位，会进行覆盖，所以事先保存待插入的元素值 
            for(j=i-1;j>=0 && arr[j]>save;j--)//只要比 待插入的元素值 大，都要往后移位 
            {
                arr[j+1] = arr[j];
            }
            arr[j+1] = save;//移位结束，腾出的位置就是 放置待排序的元素 的合适位置 
        }
        //打印当前数组的元素 
        printf("第%2d趟排序,", i);
		print_arr(arr, len);
		printf("\n"); 
    }
}
 
int main(int argc, char *argv[])
{
	int arr[] = {118,76,98,57,67,105,43,22,35,82,1};//待排序的数组 
    int len = sizeof(arr)/sizeof(arr[0]);//求数组元素个数
    printf("排序前:    ");
	print_arr(arr, len);//打印数组 
	printf("\n");
	straight_insertion_sort(arr, len);//进行直接插入排序
	 
	return 0;
}

运行结果：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/511418

数据结构与算法 排序_数据结构与算法排序

数据结构与算法 排序

数据结构与算法排序_数据结构与算法排序

数据结构与算法排序