C++数据结构X篇_20_选择排序

1. 选择排序原理

选择排序：相对于冒泡排序，减少了交换次数，下图展示了选择排序的原理，具体仍需要结合代码分析。

2. 选择排序原理核心代码

//选择排序
void select_sort(int arr[], int length)
{int min = 0;for (int i = 0; i < length; i++){int min = i;for (int j = i + 1; j < length; j++){if (arr[j] < arr[i]){min = j;}}if (min != i){swap(&arr[i], &arr[min]);}}
}

3. 选择排序时间消耗

整体代码：

#include <iostream>
#include <time.h>
#include <sys/timeb.h>using namespace std;#define MAX 10000//获取系统当前时间,ms为单位
long getSystemTime()
{struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm;
}void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//打印数组
void printArr(int arr[])
{for (int i = 0; i < 10; i++){cout << arr[i] << endl;}
}//选择排序
void select_sort(int arr[], int length)
{int min = 0;for (int i = 0; i < length; i++){int min = i;for (int j = i + 1; j < length; j++){if (arr[j] < arr[i]){min = j;}}if (min != i){swap(&arr[i], &arr[min]);}}
}int main()
{int arr[MAX];//生成随机数srand((unsigned int)time(NULL));for (int i=0;i<MAX;i++){arr[i] = rand() % MAX;}long tStart = getSystemTime();select_sort(arr, MAX);long tEnd = getSystemTime();cout << tEnd - tStart << endl;system("pause");return 0;
}

运行结果：时间消耗424ms，比冒泡排序改进版的时间消耗也少了很多

4. 选择排序