标签: selection-sort

我试图理解插入排序和选择排序之间的差异.

它们似乎都有两个组件:未排序列表和排序列表.它们似乎都从未排序的列表中取出一个元素并将其放入适当位置的排序列表中.我已经看到一些网站/书籍说选择排序是通过一次交换一个而插入排序只是找到正确的位置并插入它.但是,我看到其他文章说了些什么,说插入排序也交换了.因此,我很困惑.有没有规范来源？

我是Java的新手,我正在尝试编写一个选择排序程序.以下是我的代码:

public class SelectionSort {
    public static int a[] = {6, 4, 9, 3, 1, 7};

    public static void main(String[] args) {
        int min, i, j;
        for(i = 0; i < a.length - 1; i++) {
            min = i ;
            for(j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j; 
                }
                if (min != i) {
                    int temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;
                }
            }
        }
        for (i = …

我正在研究一种旨在按升序排序数组的方法.该数组由地震标记对象组成,我需要做的是按对象的"数量"属性对数组进行排序.我尝试了选择排序,但似乎元素没有正确交换.

这是我的代码:

private void sortAndPrint(int numToPrint){
    Object[] quakeArray= quakeMarkers.toArray();

    int indexMax;
    for(int i=0; i<quakeArray.length-1; i++) {
        indexMax = i;
        float max = ((EarthquakeMarker)(quakeArray[i])).getMagnitude();

        for( int j =i+1; j<quakeArray.length;j++){
            if(((EarthquakeMarker)(quakeArray[j])).getMagnitude()>max)
                indexMax = j;
        }
        //swap it
        Object temp = quakeArray[i];
        quakeArray[i] = quakeArray[indexMax];
        quakeArray[indexMax] = temp;
    }
    //sort finished

    for(int i =0; i< numToPrint; i++) {
        System.out.println(((EarthquakeMarker)quakeArray[i]).getProperty("title").toString());
    }
}

事实证明,地震并没有按其大小排序.

从我的角度来看,交换可能有问题,因为Java正在通过值传递.如果是这样,我该如何解决？或问题是否存在于其他地方？

我已经实现了两种算法,用于从最高到最低排序元素.

第一个,在实际RAM模型上采用二次时间,第二个采用O(n log(n))时间.第二个使用优先级队列来减少.

以下是时间,它是上述程序的输出.

• 第一列是随机整数数组的大小
• 第二列是O(n ^ 2)技术的秒数

• 第三列是O(n log(n))技术的秒数

   9600  1.92663      7.58865
   9800  1.93705      7.67376
  10000  2.08647      8.19094
  

  Run Code Online (Sandbox Code Playgroud)

尽管复杂性存在很大差异,但对于所考虑的阵列大小,第3列大于第2列.为什么会这样？C++的优先级队列实现是否缓慢？

我在Windows 7上运行此代码,Visual Studio 2012 32位.

这是代码,

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <Windows.h>
#include <assert.h>

using namespace std;

double time_slower_sort(vector<int>& a) 
{
    LARGE_INTEGER frequency, start,end;
    if (::QueryPerformanceFrequency(&frequency) == FALSE  ) exit(0);
    if (::QueryPerformanceCounter(&start)       == FALSE  ) exit(0);

    for(size_t i=0 ; i < a.size() ; ++i)  
    {

        vector<int>::iterator it = max_element( a.begin() …

我正在尝试将此选择排序从高到低编写,我不太清楚如何做到这一点.我对排序算法很陌生.

public  void selectionSort(String[ ] data){
    // for each position, from 0 up, find the next smallest item 
    // and swap it into place
    for (int place=0; place<data.length-1; place++){
        int minIndex = place;
        for (int sweep=place+1; sweep<data.length; sweep++){
            if (data[sweep].compareTo(data[minIndex]) < 0)
                minIndex=sweep;
        }
        swap(data, place, minIndex);
    }
}

我试图改变它的原因是这里的选择排序贯穿数组的剩余部分,寻找最小值然后将其交换到前面.我想改变算法以便它也看起来对于剩余部分中的最大值,并将其交换到后面,以便它同时从前面和后面建立一个排序列表.

所有帮助将不胜感激:)

好的,我一直在使用这段代码对整数进行选择排序:

public void selectSort(int [] arr)
{
    //pos_min is short for position of min
    int pos_min,temp;

    for (int i=0; i < arr.Length-1; i++)
    {
        pos_min = i; //set pos_min to the current index of array

        for (int j=i+1; j < arr.Length; j++)
        {
            if (arr[j] < arr[pos_min])
            {
                //pos_min will keep track of the index that min is in, this is needed when a swap happens
                pos_min = j;
            }                                          
        }

        //if pos_min no longer equals i than a smaller …

我想知道为什么这段代码没有输出正确的数字序列（升序）。它取自此材料 -升级选择排序。例如，当我插入这样的数组值时 - [8,5,6,1,4,7,3,0,2,9] 它返回 - [0,1,3,4,5,7,8, 6,2,9]。

#include<iostream>
using namespace std;

void Swap(int Arr[100],int Temp_min,int Temp_max)
{
    int temp;
    temp = Arr[Temp_min];
    Arr[Temp_min] = Arr[Temp_max];
    Arr[Temp_max] =temp;
}

void OptimizedSelectSort(int Arr[],int n)
{
    int i,j,min,max;

    for(i=0;i<n/2;i++)
    {
        min = i;
        max = i;
        for(j=i+1;j<n-i;j++)
        {
            if (Arr[j]> Arr[max])
            {
                max = j;
            }
            else if (Arr[j]< Arr[min])
            {
                min = j;
            }
        }
        if (i == max && n-1-i == min)
        {
            Swap(Arr,min,max);
        }
        else
        {
            if …

我一直在做一些关于替换选择排序的研究,我找不到它的任何实现或者在任何地方进行更换选择排序的良好,彻底的实现!也许我看起来不够努力,但谷歌将替换选择排序与选择排序混淆......所以这让我感到疑惑:

选择排序和替换选择排序之间的真正区别是什么？

我在哪里可以找到替换选择排序的实现(或编写它的指南)？

更换选择排序的特征是什么,使其比其他排序算法更理想？

这个算法是否被其他任何名称所知？

我正在尝试在Dafny中实现选择排序.

我sorted和FindMin函数确实有效,但selectionsort它本身包含Dafny无法证明的断言,即使它们是正确的.

这是我的计划:

predicate sorted(a:array<int>,i:int)
  requires a != null;
  requires 0 <= i <= a.Length;
  reads a;
{
  forall k :: 0 < k < i ==> a[k-1] < a[k]
}
method FindMin(a:array<int>,i:int) returns(m:int)
  requires a != null;
  requires 0 <= i < a.Length;
  ensures i <= m < a.Length;
  ensures forall k :: i <= k < a.Length ==> a[k] >= a[m];
{
  var j := i;
  m := i;
  while(j < a.Length) …

我已经编写了这两种排序算法,看起来选择排序比合并排序更快,这肯定不是正确的吗？我的测试数据是10个大小为5000到50000的随机数组,其中数组中最大可能的数字是100这是我的选择排序实现:`int i,j,iMin; int n = c.length;

    startTime = System.currentTimeMillis();
    for (i = 0; i < n - 1; i++) 
        {
        iMin = i;
            for (j = i + 1; j < n; j++)

                if (c[j] < c[iMin])
                {
                    iMin = j;
                    if(sorting)
                    {
                    theDelay();
                    }
                }
                if (iMin != i) 
                {
                    swap(c, iMin, i);
                    if(sorting)
                    {
                    theDelay();
                    }
                }

        }
   endTime = System.currentTimeMillis();
   overallTime = endTime - startTime;
  // System.out.println(overallTime);

}`

该theDelay()方法只是延迟排序算法在其中运行的线程,以便可视化图形可以绘制到JPanel以显示操作中的排序,在此测试用例中它被忽略,因此不会影响我的排序时间.

这是我的合并排序实现:

public void mergeSort(int[] d) throws …