选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

  选择排序就是从当前未排序的整数中找一个最小的整数，将它放在已排序的整数列表的最后。

  如何找出最小的一个元素呢？ 先随便选一个元素假设它为最小的元素（默认为序列的第一个元素），然后让这个元素与序列中的每一个元素进行比较，如果遇到比自己小的元素，那更新最小值下标，直到把序列中的元素遍历完，那最后的最小值就是序列中的最小值。

  例如： 使用选择排序算法将数组 { 4,2,8,0,5,7,1,3,6,9 } 进行升序排序。
  步骤：1. 在一个长度为n的无序数组中，第一次遍历n-1个数找到最小的和第一个数交换。
     2. 第二次从下一个数开始遍历n-2个数，找到最小的数和第二个数交换。
     3. 重复以上操作直到第n-1次遍历最小的数和第n-1个数交换，排序完成。

  实现代码如下所示。

#include<iostream>
using namespace std;

void SelectSort(int *list, const int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;  //min为最小值索引
		for (int j = i + 1; j < n; j++)
		{
			if (list[j] < list[min])
			{
				min = j;
			}
		}
		std::swap(list[i], list[min]);
	}
}

int main()
{
	int a[] = { 4,2,8,0,5,7,1,3,6,9 };

	cout << "排序前：" << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;

	SelectSort(a, 10);

	cout << "排序后：" << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
	system("pause");

	return 0;
}

排序前：
4 2 8 0  5 7 1 3 6 9
排序后：
0 1 2 3 4 5 6 7 8 9

  选择排序算法的详细过程如下图所示。

  时间复杂度： 对于长度为$n$的数组，代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句了。外层for循环执行 $n-1$次，那么交换（swap）就执行$n-1$次，时间复杂度为$O(n)$；内层for循环中的比较语句执行次数为$(n-1)+(n-2)+\dots +2+1=\frac{n(n-1)}{2}=\frac{1}{2}{n}^2-\frac{1}{2}n$，时间复杂度为$O(n^2)$。所以，选择排序算法的时间复杂度为$O(n^2)$。

  空间复杂度： $O(1)$。

  稳定性： 由于选择元素之后会发生交换操作，有可能把前面的元素交换到后面，所以选择排序不是稳定的排序，如下图所示。

C语言学习交流群：648422161。志同道合的小伙伴可以进群交流哦！
对于选择排序，咱们首先理解排序的思想。给定一个数组，这种思想首先假定数组的首元素为最大或者最小的。此时就要利用3个变量表示元素的下标。一个表示当前，一个表示找到的最大或者最小的下标，一个用于存放每次循环中最大值的下标。在掌握了程序的基本思想之后，再进行排序。找到最大的下标后赋给每次除非的那个最大的下标。找到之后判断所假设的当前值是否为此次循环的最大值，如果不是，就交换最大 与当前的值，从而将数组以一定的顺序排放。其实 简而言之就是每次找到最大的或者最小的放在前面，当然了排过的位置就不用多次排了

初始的一组数

45 10 5 60 9

找到最小的 5，交换位置
5 10 45 60 9

除去排好的位置接着往后
5 9 45 60 10 

以此类推直到排好。
下面贴出代码

void selectSort(int data[],int length){
    for (int i = 0; i < length; i++)
    {
        int k=i;//指向当前下标i
        //找最小值的坐标
        for (int j = i+1; j < length; j++)
        {
            //如果当前值大于后一个值则k指向新下标
            if (data[k]>data[j])
            {
                k=j;
            }
        }
        //如果不等于当前下标i，交换位置
        if (k!=i)
            {
                //交换位置
                swap(&data[k],&data[i]);
            }
        
    }

}

排序方法 平均时间 最坏情况 辅助存储 是否稳定
选择排序 O(n^2) O(n^2) O(1) 不稳定

    选择排序是排序算法的一种，思想就是，每一轮寻找数组中最大的值或者最小的值，放在头部或者放入一个新的数组。这样经历一轮遍历，数组或者新数组就是排好序的，他的目的很明确，每次找最大值或者最小值。

    这个放在头部，其实头部不是固定不变的，每次都会往后移动一位，因为前面的数据都是排好序的。这种借助当前数组做排序的算法，是为了节省空间，也是一种提高效率的办法。

    以最大值为例，如何找最大值？比较嘛，默认选择第一个元素作为最大值，依次与数组中的元素比较，有比它大的，就交换，遍历完成，就找到了最大值。

#include <stdio.h>
int main()
{
	int arr[] = {6,5,4,3,2,1,7,8,9,0};
	int max = arr[0];
	for(int i=1;i<10;i++)
	{
		if(max<arr[i])
			max = arr[i];
	}
	printf("max=%d\n",max);
	return 0;
}

    这个找最大值，就是每次比较之后，如果满足条件都需要进行数组元素交换。也有一种做法，记录下标，如果换为交换下标，这样，最后遍历完成，我们取出下标对应的元素即可。

    我们来看看选择排序：

#include <stdio.h>
void selectSort(int arr[],int n)
{
	int i,j,maxIndex,tmp;
	for(i=0;i<n-1;i++)
	{
		maxIndex = i;
		for(j=i+1;j<n;j++)
		{
			if(arr[maxIndex]<arr[j])
				maxIndex = j;
		}
		tmp = arr[i];
		arr[i] = arr[maxIndex];
		arr[maxIndex] = tmp;
	}
}

int main()
{
	int arr[] = {6,5,4,3,2,1,7,8,9,0};
	selectSort(arr,10);
	for(int i=0;i<10;i++)
		printf("%d ",arr[i]);
	printf("\n");
	return 0;
}

    这种排序，我们需要额外申请一个变量来记录maxIndex或者minIndex，如果不用这个变量，我们就回到了前面提到的，每次交换数组元素。

void selectSort(int arr[], int n)
{
	int i, j, tmp;
	for (i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (arr[i] < arr[j])
			{
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

    这种排序，看起来，很像冒泡排序，不同的是，冒泡排序，每次比较的是相邻元素，选择排序比较的是固定位置的元素和集合中剩余的元素。

    我们通过示例，来直观感受一下两者的区别：

    冒泡排序：

    选择排序：

    冒泡排序算法：

void bubbleSort(int arr[], int n)
{
	int i, j, tmp;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n - 1 - i; j++) {
			if (arr[j] < arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

   代码直观比较：

    从算法的结果和特点来看，选择排序，前面的元素是排好序的，而冒泡排序，末尾的元素的排好序的。所以在冒泡排序第二层循环里面，不用每次都遍历整个数组，而是到n-1-i的位置。他们共同特点是算法复杂度是相同的，都是O(n*n)。

    这里交换元素，我们也用了一个别的变量，其实也有取巧的算法，连别的变量也不需要的，直接交换两个元素的值：

if (arr[i] < arr[j])
{
    arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

    这种办法是一种很巧妙的算法，是有计算依据的，大家可以看看如下的计算过程：

    有人可能马上觉着，这也太low了，这不就是：

//a=2,b=3
a = a + b；// a = 5
b = a - b；// b = 2
a = a - b; // a = 3

    乍一看，没毛病，这没什么好说的，但是你可能忽略的一个问题，就是计算机的整数是有范围的，在边界以内，这么来搞没问题，如果两个数字，都在边界Integer.max附近，相加就超出范围了，并不能达到预期的结果，所以说“异或”才是最安全的做法。 

    其实，这个算法的巧妙之处在于他没有借助第三个变量就交换了两个变量的值，这个算法经常在面试题中会出现，当你知道了，就会觉着很简单。

    上面介绍了选择排序的完整实现，以及各种取巧的办法。貌似很完美了，但是有个问题，就是这种排序，理论上只支持一种排序，要么升序，要么降序。如果要改变排序规则，我们需要修改交换的判断条件，需要硬编码。在c语言中，我们可以借助一个回调函数来作为判断的依据，我们在给排序算法传递参数的时候，将回调函数传进去，然后我们只需要修改回调函数的规则即可。

#include <stdio.h>

int compare(int a, int b)
{
	return a < b?1:0;
}

void selectSort(int arr[], int n, int (*pf)(int, int))
{
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (pf(arr[i], arr[j]))
			{
				arr[i] = arr[i] ^ arr[j];
				arr[j] = arr[i] ^ arr[j];
				arr[i] = arr[i] ^ arr[j];
			}
		}
	}
}

int main()
{
	int arr[] = { 6,5,4,3,2,1,7,8,9,0 };
	selectSort(arr, 10, compare);
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

    其实这个算法就很接近c语言库提供的qsort算法了，看看算法的表示：

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

   其中参数base是数组，nitems表示数组元素个数，size表示元素的长度，也就是该类型的长度，整型是4，比较函数两个参数都是const void *，表示任意类型，并不局限于int。 

    利用qsort排序示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b)
{
	int* ia = (int*)a;
	int* ib = (int*)b;
	return *ia > *ib ? 1 : 0;
}
int main()
{
	int arr[] = { 6,5,4,3,2,1,7,8,9,0 };
	qsort(arr, 10, 4, compare);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

    区别在于可以对各种类型的数据进行排序，不仅局限于整型。他可以对int,char,double进行排序。

    我们需要注意的是这里对于字符串数组的排序，字符串可以表示为char *，字符串数组就是char **了。我们在设置回调函数作为判断条件的时候，需要对回调函数做正确的参数设置，void*这时候需要转为char**才是表示的字符串地址。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* a, const void* b)
{
	return strcmp(*(char**)a, *(char**)b)>0?1:-1;
}
int main()
{
	const char * fruit[] = {"banana","apple","orange","grapefruit","strawberry"};
	int size = sizeof(fruit) / sizeof(fruit[0]);
	qsort(fruit, size , sizeof(char*), compare);
	for (int i = 0; i < size; i++)
	{
		printf("%s\n", fruit[i]);
	}
	return 0;
}

    以上是对选择排序的理解和整理，示例也通过vs2019编译通过。我这里遇到了一个问题，就是sizeof(char*)在64位机器下是8。