数据结构实验之排序二：交换排序

比眉伴天荒 2022-12-29 01:52 19阅读 0赞

## 数据结构实验之排序二：交换排序 ##

Description  
冒泡排序和快速排序都是基于"交换"进行的排序方法，你的任务是对题目给定的N个（长整型范围内的）整数从小到大排序，输出用冒泡和快排对这N个数排序分别需要进行的数据交换次数。

Input  
连续多组输入数据，每组数据第一行给出正整数N(N ≤ 10^5)，随后给出N个整数，数字间以空格分隔。

Output  
输出数据占一行，代表冒泡排序和快速排序进行排序分别需要的交换次数，数字间以1个空格分隔，行末不得有多余空格。

Sample  
Input  
8  
49 38 65 97 76 13 27 49  
Output  
15 9  
Hint  
**注意：数据相等时不做交换**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int a[100010], b[100010], n;
    int sum1, sum2;
    void sort(int* a, int l, int r)//快速排序
    {
        
    	int i = l, j = r;
    	if (i >= j)
    		return;
    	int key = a[i];
    	while (i < j)
    	{
        
    		while (i < j && key <= a[j])
    			j--;
    		if (a[i] != a[j])//数据不相等，交换次数+1
    		{
        
    			sum1++;
    			a[i] = a[j];
    		}
    		while (i < j && key >= a[i])//数据不相等，交换次数+1
    			i++;
    		if (a[i] != a[j])
    		{
        
    			sum1++;
    			a[j] = a[i];
    		}
    	}
    	a[i] = key;
    	sort(a, l, i - 1);
    	sort(a, i + 1, r);
    }
    void mp(int* b, int n)//冒泡排序
    {
        
    	int i, j, temp;
    	for (i = 0; i < n - 1; i++)
    	{
        
    		for (j = 0; j < n - 1 - i; j++)
    		{
        
    			if (b[j] > b[j + 1])
    			{
        
    				sum2++;
    				temp = b[j];
    				b[j] = b[j + 1];
    				b[j + 1] = temp;
    			}
    		}
    	}
    }
    int main()
    {
        
    	int i;
    	while (~scanf("%d", &n))
    	{
        
    		for (i = 0; i < n; i++)
    		{
        
    			scanf("%d", &a[i]);//输入数组a，同时将数组a复制给数组b，数组a快排后，改变了数组a的原有顺序，所以应该使用 一个新的数组a
    			b[i] = a[i];
    		}
    		sum1 = sum2 = 0;
    		sort(a, 0, n - 1);
    		mp(b, n);
    		printf("%d %d\n", sum2, sum1);
    	}
    }