标签: selection-sort

我正在努力在字符串的ArrayList上进行选择排序以按字母顺序排列它们.我不知道我做错了什么.但它对我来说不合适.继承我的代码.

    ArrayList<String> list = new ArrayList<String>();
    list.add("a");
    list.add("d");
    list.add("f");
    list.add("c");
    System.out.println(list);
    int i;
    int j;
    int minValue;
    int minIndex;

    for (i=0; i<list.size(); i++) {
        System.out.println(list.get(i));
        char iLetter = (list.get(i).charAt(0));
        int iValue = (int) iLetter;
        minValue = iValue;
        minIndex = i;
        for(j=i; j<list.size(); j++) {
            char jLetter = list.get(j).charAt(0);
            int jValue = (int) jLetter;
            if (jValue < minValue) {
                minValue = jValue;
                minIndex = j;
            }
        }
        if(minValue < iValue) {
            int temp = iValue;
            char idx = list.get(minIndex).charAt(0);
            int idxValue …

我正在尝试编写一个名为selection_sort. 这个函数应该，当出现一个由 n 个整数组成的数组时，搜索数组以找到最大的元素，然后将它移动到数组的最后一个位置。完成此操作后，它应该递归调用自身以对数组的前 n-1 个元素进行排序。

这是我的代码：

#include <stdio.h>

void selection_sort(int [], int);

int main(void)
{
  int n, a[n];
  printf("How many numbers do you wish to sort? ");
  scanf("%d", &n);

  printf("Well go on, type them in... "); 
  for(int i = 0; i < n; i++)
    scanf("%d", &a[i]);

  selection_sort(a, n); 

  printf("Here is the sorted array: ");
  for(int i = 0; i < n; i++) 
    printf("%d ", a[i]);
  printf("\n");

 return 0;
}

void selection_sort(int a[], int n)
{
  if(n == …

当插入排序和冒泡排序为O(n)时,为什么选择排序O(n ^ 2)的最佳情况时间复杂度？他们的平均时间是一样的.我不明白为什么最好的案例时间是不同的.会感激一些帮助.

我发现选择排序使用蛮力策略。但是，我认为它使用了贪婪策略。

为什么我认为它使用 Greedy：它在外循环从 0 到 n-1，从 i+1 到 n-1。这真是太天真了。它在每次迭代中选择一个中的最小元素——它在本地选择最好的。一切都像贪婪，但事实并非如此。

你能解释一下为什么这不是我的想法吗？我在 Internet 上没有找到有关此问题的信息。

我相信选择排序有以下行为:

最佳案例:由于所有元素排列正确,因此无需交换

最坏的情况:需要n-1次交换,即每次传递需要交换,并且有n-1次传递,因为我们知道其中n是数组中的元素数量

平均情况:无法找到这个.找到它的程序是什么？

以上信息是否正确？

这表示交换的时间复杂度在最好的情况下是O(n) http://ocw.utm.my/file.php/31/Module/ocwC​​hp5SelectionSort.pdf

选择排序的意义是什么？即使在最好的情况下，它的时间复杂度也是 O(n^2)。那么为什么它仍然盛行？

我有一个实现选择排序算法的简单示例：

int main(){

    vector<int> vi{ 5, 7, 23, 7, 23, 5, 
    77, 10, 57, 23,  2  };
    int min = 0;
    for(int i = 0; i < vi.size() - 1; ++i){
        min = i;
        for(int j = i + 1; j < vi.size(); ++j){
            if(vi[j] < vi[min]){
                min = j;
            }
        }
            vi[i] ^= vi[min];
            vi[min] ^= vi[i];
            vi[i] ^= vi[min];
     //int tmp = vi[i];
            //vi[i] = vi[min];
            //vi[min] = tmp;
    }

    for(auto i : vi)
        cout << i << …

合并排序 (nlogn) 的效率总是比选择排序 (n^2) 快。你什么时候会选择选择而不是合并排序？

#include<stdio.h>
#include<conio.h>

float smallest(int arr[],int k,int n);
void sort(int arr[],int n);

void main()
{
 int arr[20],i,n,j,k;
 clrscr();
 printf("\nEnter the number of elements in the array: ");
 scanf("%d",&n);

 printf("\nEnter the elements of the array");
 for(i=0 ; i < n ; i++)
 {
  printf("\n arr[%d] = ",i);
  scanf("%d",&arr[i]);
 }

 sort(arr,n);
 printf("\nThe sorted array is: \n");
 for(i=0 ; i < n ;  i++)
 printf("%d\t",arr[i]);
 getch();
}

int smallest(int arr[],int k,int n)//smallest function
{
 int pos=k,small=arr[k],i;
 for(i=k+1;i<n;i++)
 {
  if(arr[i]<small)
  {
   small=arr[i];
   pos=i;
  }
 } …

我在Haskell中寻找以下选择排序代码的非尾递归版本：

import Data.List (minimum, delete)

ssort :: Ord t => [t] -> [t]
ssort [] = []
ssort xs = let { x = minimum xs } in  x : ssort (delete x xs)

您能否提供选择排序的非尾递归版本？

我知道更改原始代码不是一个好主意，但我需要该版本才能进行实验。