首页 > 试题广场 >

在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的

[单选题]

在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是(    )

  • 希尔排序
  • 冒泡排序
  • 插入排序
  • 选择排序

堆选归基与初始序列无关,堆选快希不稳定。

发表于 2018-07-19 17:21:16 回复(0)
比较排序算法(Comparison Sorts)

Category

Name

Best

Average Worst Memory Stability

插入排序

(Insertion Sorts)

插入排序

(Insertion Sort)

n

n2

n2

1

Stable

希尔排序

(Shell Sort)

n

n log2n

n log2 n

1

Not Stable

交换排序

(Exchange Sorts )

快速排序

(Quick Sort)

n log n

n log n

n2

log n

Not Stable

冒泡排序

(Bubble Sort)

n

n2

n2

1

Stable

鸡尾酒排序

(Cocktail Sort)

n

n2

n2

1

Stable

奇偶排序

(Odd-Even Sort)

n

n2

n2

1

Stable

选择排序

(Selection Sorts)

选择排序

(Selection Sort)

n2

n2

n2

1

Not Stable

堆排序

(Heap Sort)

n log n

n log n

n log n

1

Not Stable

合并排序

(Merge Sorts)

合并排序

(Merge Sort)

n

n log n

n log n

n

Stable

混合排序

(Hybrid Sorts)

内省排序

(Introspective Sort)

n log n

n log n

n log n

log n

Not Stable

编辑于 2018-10-17 14:21:08 回复(0)
概念:选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 (百度的)
从以上概念可以看出来,不管初始顺序是什么,比较的次数都是不变的

发表于 2017-12-10 20:49:07 回复(1)
以下代码可供参考:
#include <iostream>
using namespace std;
int slectionSort(int arr[],int n) 
{     int min;     int i,j;     int t;     for(i=0;i<n-1;i++)     {         min = i;         for(j=i+1;j<n;j++)         {             if(arr[j]<arr[min])             {                 min = j;             }         }         if(i!=min)         {             t = arr[i];             arr[i] = arr[min];             arr[min] = t;         }     }
}

int main()
{     int arr[] = {4,3,67,232,44,1,0,8};     slectionSort(arr,8);     for(int i = 0;i<8;i++)     {         cout<<arr[i]<<" ";     }     cout<<endl;
}

发表于 2017-12-10 21:27:51 回复(0)