如何优化排序算法

ruru对于只有四个元素的数组，选择排序和冒泡排序的效率差异不大，因为它们的复杂度都是O(n^2)，但由于n很小，实际运行时间差异并不明显。然而，对于优化，我们可以考虑以下几种方法：

1. 冒泡排序：由于数组很小，冒泡排序可以是一个简单且直观的选择。

2. 插入排序：对于小数组，插入排序通常比选择排序和冒泡排序更快，因为它的最好情况时间复杂度是O(n)。

3. 直接构造：由于数组只有四个元素，我们可以直接找出最大值和最小值，而不需要完整的排序。

以验证卡布列克运算为例：若使用交换排序法，则如下：

#include<stdio.h>
void h(int n,int m);
int main()
{
	int n;
	printf("Enter number:");
	scanf("%d",&n);
	
	int m=0;
	h(n,m);
	return 0;
}
void h(int n,int m)
{
	int a[4];
	for(int i=0;i<4;i++)
	{
		a[i]=n%10;
		n/=10;
	}
	for(int i=0;i<3;i++)
	{
		int min_i=i;
		int t;
		for(int j=i+1;j<4;j++)
		{
			if(a[j]<a[min_i])
			{
				min_i=j;
			}
		}
			if(min_i!=i)
			{
				t=a[i];
				a[i]=a[min_i];
				a[min_i]=t;
			}
		
	}
	int min=a[0]*1000+a[1]*100+a[2]*10+a[3];
	int max=a[3]*1000+a[2]*100+a[1]*10+a[0];
	printf(" [%d]:%d-%d=%d\n",m+1,max,min,max-min);
	if((max-min)!=6174)
	{
		h(max-min,m+1);
	}
}

如果换作直接构造最大值最小值则会简化代码，如下： 

#include <stdio.h>

void kaprekar(int n, int step) {
    int digits[4], i, max, min, temp;
    
    // 分解数字为单独的数字
    for (i = 0; i < 4; i++) {
        digits[i] = n % 10;
        n /= 10;
    }
    
    // 直接构造最大值和最小值
    max = min = 0;
    for (i = 0; i < 4; i++) {
        // 找到最大值
        int max_index = 0;
        for (int j = 1; j < 4; j++) {
            if (digits[j] > digits[max_index]) {
                max_index = j;
            }
        }
        max = max * 10 + digits[max_index];
        digits[max_index] = -1; // 使用-1标记已使用过的数字
        
        // 找到最小值
        int min_index = 0;
        for (int j = 1; j < 4; j++) {
            if (digits[j] > -1 && (digits[min_index] == -1 || digits[j] < digits[min_index])) {
                min_index = j;
            }
        }
        min = min * 10 + digits[min_index];
        digits[min_index] = -1; // 使用-1标记已使用过的数字
    }
    
    // 打印结果
    printf(" [%d]:%d-%d=%d\n", step, max, min, max - min);
    
    // 如果不是6174，递归调用
    if (max - min != 6174) {
        kaprekar(max - min, step + 1);
    }
}

int main() {
    int number;
    printf("Enter number: ");
    scanf("%d", &number);
    
    // 检查输入是否为四位数
    if (number < 1000 || number > 9999) {
        printf("Please enter a four-digit number.\n");
        return 1;
    }
    
    kaprekar(number, 1);
    return 0;
}

两种方法的不同在于后者不需要交换a[i]和每次循环得到的最小值，我们没有使用排序算法，而是构造了最大值和最小值。我们遍历数组，每次找到最大和最小的数字，然后将它们分别添加到最大值和最小值中，并标记为已使用。这种方法避免了排序，对于四个元素的数组来说，它非常高效。