数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚设计
法学一种对选择排序略有改进的排序算法？
这里我们来看看一些对选择排序的改进。众所周知，选择排序的工作原理是取数组中的最小或最大元素，然后将该元素放在正确的位置。在这种方式中，我们希望对数组按两种方式进行排序。这里我们将同时取最大值和最小值，然后从两个末端对数组进行排序。让我们看看算法来获取更好的思路。
算法
twoWaySelectionSort(arr, n)
begin for i := 0, and j := n-1, increase i by 1, and decrease j by 1, until i>=j, do min := minimum element from index i to j max := maximum element from index i to j i_min := index of min i_max := index of max exchange the arr[i] and arr[i_min] if arr[i_min] is same as max, then swap arr[j] and arr[i_min] else swap arr[j] and arr[i_max] end if done end
示例
#include<iostream>
using namespace std;
void twoWaySelectionSort(int arr[], int n) {
//i will move from left, and j will move from right
for (int i = 0, j = n - 1; i < j; i++, j--) {
int min = arr[i], max = arr[i];
int i_min = i, i_max = i; //i_min and i_max will hold min and max index respectively
for (int k = i; k <= j; k++) {
if (arr[k] > max) {
max = arr[k];
i_max = k;
} else if (arr[k] < min) {
min = arr[k];
i_min = k;
}
}
swap(arr[i], arr[i_min]); //put the min into the index i
if (arr[i_min] == max)
swap(arr[j], arr[i_min]);
else
swap(arr[j], arr[i_max]);
}
}
main() {
int arr[] = { 25, 45, 14, 10, 23, 29, 65, 21, 78, 96, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
twoWaySelectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}输出
Sorted array: 10 14 21 23 25 29 30 45 65 78 96
更新于：2019 年 7 月 30 日
225 次浏览
广告