排序2-选择排序
每次找到最值的下标, 最后交换元素, 每次遍历的元素减少. 减少了交换元素的次数. 性能较冒泡排序更好一点, 但时间复杂度仍是$O(n^2)$
交换元素
//交换
void Swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
打印数组
void PrintArray(int arr[]){
int len = MAX;
for (int i = 0; i < len; i++){
cout << arr[i] << " ";
}
cout << endl;
}
选择排序
void SelectSort(int arr[], int length){
for (int i = 0; i < length; i++){
int min = i; //默认第一个为最小元素
for (int j = i+1; j < length; j++){
if(arr[j]>arr[min])
min = j; //更新最小元素的下标
}
if(min!=i) //如果最小元素不是初始值, 就交换位置
Swap(&arr[min],&arr[i]);
}
}
冒泡排序
void BubbleSort(int arr[]){
int flag = 0; //0表示false, 标志没有排序好
int len = MAX;
for (int i = 0; i<len; i++){
flag = 1; //如果flag没有被更新为0, 认为已经排序好了
for (int j = 0; j < len-1-i; j++){
if(arr[j]>arr[j+1]){
flag = 0; //认为没有排序好
Swap(&arr[j], &arr[j+1]);
}
}
}
}
测试
int main(){
int arr[MAX];
srand((unsigned int)time(NULL));
for (int i = 0; i < MAX; i++){
arr[i] = rand() % MAX;
}
int arr2[MAX];
srand((unsigned int)time(NULL));
for (int i = 0; i < MAX; i++){
arr2[i] = rand() % MAX;
}
long t1 = getSystemTime();
SelectSort(arr,MAX);
long t2 = getSystemTime();
long t3 = getSystemTime();
BubbleSort(arr);
long t4 = getSystemTime();
cout << "选择排序时间:" << t2-t1 << endl;
cout << "冒泡排序时间:" << t4-t3 << endl;
system("pause");
return 0;
}
标签:arr,min,int,MAX,选择,++,排序
From: https://www.cnblogs.com/HIK4RU44/p/18149639