課題31 給出一組實驗來比較下列排序演算法的時間效能快速排

1樓：匿名使用者

7個以下資料，插入排序有效率。

以上資料，安排有序(順序，逆序)，隨機數多組進行測試。

一般來說，快排最快，但是原始資料有序情況下會退化為n平方，需要隨機化。

在待排序的資料表已經為有序時,下列排序演算法中花費時間反而多的是a堆排序b希爾排序c氣泡排序d快速排序

2樓：匿名使用者

快速排序花費時間最多

3樓：苟祥明

c 氣泡排序花費時間最多o(n²)

在氣泡排序,希爾排序,基數排序,歸併排序四種排序演算法中不穩定的排序演算法是

4樓：

希爾排序是不穩定的，它需要多次的插入排序，步長逐漸變小，在不同的插入排序過程中可能會出現相同的元素交叉移動的情況，因此是不穩定排序演算法

5樓：孑然丁仔

希爾排序是不穩定的。八大排序演算法中除希爾排序外，還有快速排序，簡單選擇排序，堆排序也是不穩定的。

對同一個基本有序的待排序列分別進行堆排序、快速排序和氣泡排序,最省時間的演算法是___________

6樓：仁昌居士

對同一個基本有序的待排序列分別進行堆排序、快速排序和氣泡排序，最省時間的演算法是氣泡排序。

氣泡排序的最好比較次數為n次，最差比較次數為n＾2次，最差比較次數為0次，最差比較次數為n＾2次，最差比較次數為1次，最差比較次數為1次。

快速排序的最好比較次數為nlogn次，最差比較次數為n＾2次，最差比較次數為logn次，最差比較次數為n次，最差比較次數為logn次，最差比較次數為n次。

堆排序的最好比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為1次，最差比較次數為1次。

7樓：匿名使用者

是氣泡排序，氣泡排序、快速排序、堆排序的效能比較對照

排序方法比較次數移動次數穩定性輔助空間

最好最差最好最差最好最差

氣泡排序 n n^2 0 n^2 是 1 1

快速排序 nlogn n^2 logn n 否 logn n

堆排序 nlogn nlogn nlogn nlogn 否 1 1

而當待排序列已基本有序時，對氣泡排序來說是最好情況，對快速排序來說就是最差情況，而堆排序則最好最差都一樣。因此本題答案是氣泡排序。

8樓：王章婷

快速排序，因為從平均效能而言，快速排序最佳，其所需時間最省

設表中元素的初始狀態是按鍵值遞增的,分別用堆排序、快速排序、氣泡排序和歸併排序方法對

9樓：擰萌啊糕

簡單排序的演算法（直接插入，冒泡，簡單選擇排序）簡單且穩定，適合與待排記錄較小的情況，噹噹待排序的關鍵碼序列已經基本有序時，用直接插入排序最快。

就平均時間的效能而言，快速排序最佳，即排序速度最快，所以在隨機情況下，快速排序是最佳選擇。一般情況下，快速排序效率最好。

既要節省空間，又要有較快的排序速度，堆排序是最佳選擇，其不足之處是建堆時需要消耗較多時間。

若希望排序是穩定的，且有較快的排序速度，則可選用2路歸併排序，其缺點需要較大的輔助空間分配。

10樓：你de淚凌亂了

因為氣泡排序第一趟如果沒有發生任何一次交換的話就說明本身是有序的不需要再進行排序了。然後題目的條件就是初始就是按照遞增順序的。

下列那種排序方法更適合於外部排序() 選擇排序插入排序氣泡排序歸併排序

11樓：人生不變的寶貝

選擇排序、快速排序、希爾排序、堆排序不是穩定的排序演算法，而氣泡排序、插入排序、歸併排序和基數排序是穩定的排序演算法

比較直接插入排序，簡單選擇排序，快速排序，堆排序，歸併排序，希爾排序和基數排序的時空效能穩定性和情

12樓：寶石鯊魚

堆排序 n*logn 時間在這裡比較優不過穩定性差快排 o(nlogn)，最壞情況為o(n^2)。在實際應用中，快速排序的平均時間複雜度為o(nlogn)。

比較均衡

直接插入排序，簡單選擇排序 n^2

希爾排序和基數排序不太瞭解

空間的話個人認為是一樣的因為你要用同樣的陣列去存只是存的順序不同罷了

時間的話 100w以內快排最優 100w以上堆排的優越性就明顯出來了

所以一般快排就可以滿足

利用插入排序，希爾排序，起泡排序，快速排序，選擇排序，堆排序，歸併排序排序方法排序30000個隨機整數

13樓：智慧的默默

#include"stdio.h"

#include "stdlib.h"

#include

#include"time.h"

#include

using namespace std;

void insertsort(int* pdataarray, int idatanum)

pdataarray[k] = temp; //插入

} }

} //交換data1和data2所指向的整形

void dataswap(int* data1, int* data2)

*函式名稱：selectionsort

*引數說明：pdataarray 無序陣列；

* idatanum為無序資料個數

*說明：選擇排序

void selectionsort(int* pdataarray, int idatanum)

}*函式名稱：shellinsert

*引數說明：pdataarray 無序陣列；

* d 增量大小

* idatanum為無序資料個數

*說明：希爾按增量d的插入排序

void shellinsert(int* pdataarray, int d, int idatanum)

if (j != i - d) //存在比其小的數

pdataarray[j+d] = temp;

} }

*函式名稱：shellsort

*引數說明：pdataarray 無序陣列；

* idatanum為無序資料個數

*說明：希爾排序

void shellsort(int* pdataarray, int idatanum)

}*函式名稱：bubblesort

*引數說明：pdataarray 無序陣列；

* idatanum為無序資料個數

*說明：氣泡排序

void bubblesort(int* pdataarray, int idatanum)

int partions(int l,int low,int high)

if(rchild<=size&&a[rchild]>a[max])

if(max!=i)

}}void buildheap(int *a,int size) //建立堆

}void heapsort(int *a,int size) //堆排序

} void mergearray(int a, int first, int mid, int last, int temp)

while (i <= m)

temp[k++] = a[i++];

while (j <= n)

temp[k++] = a[j++];

for (i = 0; i < k; i++)

a[first + i] = temp[i];

} void mergesort(int a, int first, int last, int temp)

}bool mergesort(int a, int n)

int main(int argc, char* argv)

insertsort(aa,30000);

double e=(double)(end.quadpart-start.quadpart)/ (double)freq.quadpart;

printf("插入排序%.10f seconds\n",e);

selectionsort(aa,30000);