C语言程序设计十大排序—选择排序

1.概念✅

  排序是数据处理的基本操作之一，每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法，排序后的数据更易于处理和查找。在计算机发展的历程中，在排序算法的研究一直深受人们重视，出现了很多算法，在思路、效率、应用等方面各有特色。通过学习排序算法，读者可以理解不同算法的优势和局限性，并根据具体情况选择最合适的算法，以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力，在解决其他类型的问题时也能够应用到类似的思维方法。

2.选择排序🎈

  选择排序（Selection Sort）是最简单、直观的排序算法，虽然效率不高，但是利于理解和实现。
  排序的目的是什么？例如对n个数从小到大排序，就是把杂乱无序的n个数放到它们应该放的位置上。
  最直接的做法是找到最小数，放在第1个位置，找到第2个小的数，放在第2个位置，......，找到第n个数，放在第n个位置。
这个思路就是排序，具体操作描述如下：
  （1）第一轮，在n个数中找到最小数，然后与第1个位置的数交换，这样就把最小数放到了第一位置，如下图所示：

  （2）第二轮，在第2~n个数中找到最小值，然后与第2个位置的数交换，这样就把地2小的数放到了第2个位置，如下图所示：

  （3）第三轮，在第3~n个数中找到最小的数…
一共执行n-1轮操作，第i轮找到第i小的数，放到第i个位置，就排好序了。

3.代码实现✅

3.1 直接写✨

#include "stdio.h"
int main(){
	int a[10]={5,1,6,9,7,0,-5,10,95,63};
	int i,j,t,min;
	for(i=0;i<=9;i++)
		for(j=i+1;j<10;j++) 
			if(a[i]>=a[j]){
   				t=a[i];
               	 	a[i]=a[j];
                		a[j]=t;
			}
	printf("排序后的顺序:");
	for(i=0;i<10;i++)	
		printf("%d ",a[i]);
}

3.2 函数✨

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    // 外层循环遍历每一位
    for (i = 0; i < n - 1; i++) {
        minIndex = i;  // 假设当前元素为最小值的索引
        // 内层循环找出当前未排序部分中的最小值
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 更新最小值索引
            }
        }
        // 如果发现更小的值，交换位置
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

void printArray(int arr[], int n) {
	int  i ;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {5,1,6,9,7,0,-5,10,95,63}; // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组大小
    selectionSort(arr, n); // 调用选择排序函数
    printf("排序后的数组: \n");
    printArray(arr, n); // 打印排序后的数组
    return 0;
}

4.总结✅

  选择排序算法的计算量是多少？找最小的数需要比较n-1次，找第2小的数需要比较n-2次，......，一共需要比较n^2/2次，把它的计算复杂度记为O(n^2)。直接看代码也能得到这个结论：有两重for循环，分别循环n次，共循环O(n^2)次。
  将上述代码提交到判题系统，只能通过20%的测试。判题系统一般给一秒的执行时间，计算机一秒约能计算一亿次。本题20%的数据，有n<=10^3，能在一秒内完成。若n=10^5，选择排序需要的计算n^2=100亿次，超时。
  选择排序是一种“死脑筋”的算法，它与数据列的特征无关，不管原数据列是不是有序，都得计算O(n^2)次，上一个“冒泡算法”就聪明得多，如果第一能找到最大数发现数列已经有序，就停止不再做排序计算。
  选择排序虽然低效，但也有优点：（1）简单、易写；（2）不占用额外的空间，排序就在原理的序列上操作。

5.十大排序

1.冒泡排序