sorting
выбор
Поиск…
замечания
В информатике сортировка сортировки - это алгоритм сортировки, в частности, сортировка на месте. Он имеет временную сложность O (n 2 ), что делает его неэффективным в больших списках и, как правило, хуже, чем аналогичная сортировка вставки. Сортировка выбора отличается своей простотой и имеет преимущества производительности по сравнению с более сложными алгоритмами в определенных ситуациях, особенно там, где ограничена вспомогательная память.
На следующем рисунке показано, как работает сортировка -
Ниже псевдокода помогает создавать программу (на любом языке) или понимать сортировку выбора.
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Преимущества:
- это слишком просто понять
- он хорошо работает в небольшом списке
- никакое дополнительное временное хранилище не требуется, кроме того, что необходимо для хранения исходного списка
Ссылка на изображение: Университет RMIT
Выбор Сортировка (Python)
Анимация, чтобы показать, как работает сортировка
В приведенном ниже примере показана сортировка выбора в Python
def sort_selection(my_list):
for pos_upper in xrange( len(my_list)-1, 0, -1):
max_pos = 0
for i in xrange(1, pos_upper + 1):
if(my_list[i] > my_list[max_pos]):
max_pos = i
print "resetting max_pos = " + str(max_pos)
my_list[pos_upper], my_list[max_pos] = my_list[max_pos], my_list[pos_upper]
print "pos_upper: " + str(pos_upper) + " max_pos: " + str(max_pos) + " my_list: " + str(my_list)
return my_list
if __name__ == "__main__":
my_list = [54,26,93,17,77,31,44,55,20]
print "my_list: " + str(my_list)
print sort_selection(my_list)
Вывод программы:
my_list: [54, 26, 93, 17, 77, 31, 44, 55, 20]
resetting max_pos = 2
pos_upper: 8 max_pos: 2 my_list: [54, 26, 20, 17, 77, 31, 44, 55, 93]
resetting max_pos = 4
pos_upper: 7 max_pos: 4 my_list: [54, 26, 20, 17, 55, 31, 44, 77, 93]
resetting max_pos = 4
pos_upper: 6 max_pos: 4 my_list: [54, 26, 20, 17, 44, 31, 55, 77, 93]
pos_upper: 5 max_pos: 0 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
resetting max_pos = 4
pos_upper: 4 max_pos: 4 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
pos_upper: 3 max_pos: 0 my_list: [17, 26, 20, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 2 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 1 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
Ссылка на изображение: Pirate Learner
Выбор Сортировка (Java)
Анимация, чтобы показать, как работает сортировка
Ниже приведен пример сортировки по возрастанию:
public class MySelectionSort {
public static int[] doSelectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++)
if (arr[j] < arr[index])
index = j;
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
return arr;
}
Я написал образец метода main() чтобы показать результат сортировки выбора:
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doSelectionSort(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
Вывод программы:
2, 7, 10, 34, 42, 56, 67, 88
Ниже приведен пример сортировки по убыванию:
public static void doDescendingSelectionSort ( int [ ] num )
{
int i, j, first, temp;
for ( i = num.length - 1; i > 0; i - - )
{
first = 0; //initialize to subscript of first element
for(j = 1; j <= i; j ++) //locate smallest element between positions 1 and i.
{
if( num[ j ] < num[ first ] )
first = j;
}
temp = num[ first ]; //swap smallest found with element in position i.
num[ first ] = num[ i ];
num[ i ] = temp;
}
}
Ссылка на изображение: Wikipedia