資料結構的排序方式有那些呢？

Question

資料結構的排序方式有那些呢？
請介紹一些來看看吧！^^

麻煩寫每一種的特性！

Answer 1

Selection Sort:The selection sort algorithm sorts a list by selection the smallest element in the (unsorted portion of the) list, and then moving this smallest element to the top of the (unsorted)list.

the number of key comparisons:O(n^2)

Insertion Sort:Reduce number of key comparisons made in selection sort

the number of key comparisons:O(n^2)
the number of swap:O(n)

Quick sort:
List it partitioned into 2 sublists, and the 2 sublists are then sorted and combined into one list in such way so that the combined list is sorted

key comparions:(AVG case)..........O(n*log n) (Worst case)......O(n^2)
swap :(AVG case)..........O(n*log n) (Worst case)......O(n^2)

Merge sort:
Merge sort algorithm also partitions the list into 2 sublists, sort the sublists, and then combines the sorted sublists into one sorted list

key comparisons:
O(n*log 2n)

Heap Sort:
Def:A heap is a list in which each element contains a key, such that the key in the element at position k in the list is at least as large as the key int the element at position 2k+1(if it exits), and 2k+2(if it exits)

Answer 2

請參考：http://www.cyut.edu.tw/~ckhung/b/al/sort1.shtml

Answer 3

Quick Sort, Selection Sort, Heap Sort, Insertion Sort, Bubble Sort, Binary Tree Sort, Radix Sort ...