資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告