在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是( )
比较排序算法(Comparison Sorts) | ||||||
Category | Name | Best | Average | Worst | Memory | Stability |
插入排序 (Insertion Sorts)
| n | n2 | n2 | 1 | Stable | |
n | n log2n | n log2 n | 1 | Not Stable | ||
交换排序 (Exchange Sorts )
| n log n | n log n | n2 | log n | Not Stable | |
n | n2 | n2 | 1 | Stable | ||
n | n2 | n2 | 1 | Stable | ||
n | n2 | n2 | 1 | Stable | ||
选择排序 (Selection Sorts)
| n2 | n2 | n2 | 1 | Not Stable | |
n log n | n log n | n log n | 1 | Not Stable | ||
合并排序 (Merge Sorts) | n | n log n | n log n | n | Stable | |
混合排序 (Hybrid Sorts) | n log n | n log n | n log n | log n | Not Stable |
以下代码可供参考: #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; }