冒泡排序
??冒泡排序時通過無序區中相鄰記錄的關鍵字間的比較和位置的交換，使關鍵字最小的元素如氣泡似的逐步上浮直水面。有序區逐漸擴大，無序區逐漸縮小。
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。 針對所有的元素重復以上的步驟，除了最后一個。 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較
動畫演示
冒泡排序是一種非常容易理解的排序
普通冒泡
void bubble0 ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; for ( int i
= 0 ; i
< size
; ++ i
) { for ( int j
= 0 ; j
< size
- i
- 1 ; ++ j
) { if ( arr
[ j
] > arr
[ j
+ 1 ] ) { swap ( arr
[ j
+ 1 ] , arr
[ j
] ) ; } } }
}
優化一
void bubble1 ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; for ( int i
= 0 ; i
< size
; ++ i
) { bool flag
= true ; for ( int j
= 0 ; j
< size
- i
- 1 ; ++ j
) { if ( arr
[ j
] > arr
[ j
+ 1 ] ) { flag
= false ; swap ( arr
[ j
+ 1 ] , arr
[ j
] ) ; } } if ( flag
) return ; }
}
優化二
void bubble2 ( vector
< int > & arr
)
{ int size
= arr
. size ( ) - 1 ; int pos
= size
; for ( int i
= 0 ; i
< size
; ++ i
) { bool flag
= true ; int k
= 0 ; for ( int j
= 0 ; j
< pos
; ++ j
) { if ( arr
[ j
+ 1 ] < arr
[ j
] ) { flag
= false ; swap ( arr
[ j
+ 1 ] , arr
[ j
] ) ; k
= j
; } } if ( flag
) return ; pos
= k
; }
}
優化三
void bubble3 ( vector
< int > & arr
)
{ int size
= arr
. size ( ) - 1 ; int pos
= size
; int pos1
= 0 ; for ( int i
= 0 ; i
< size
; ++ i
) { bool flag
= true ; int k
= 0 ; for ( int j
= 0 ; j
< pos
; ++ j
) { if ( arr
[ j
+ 1 ] < arr
[ j
] ) { flag
= false ; swap ( arr
[ j
+ 1 ] , arr
[ j
] ) ; k
= j
; } } if ( flag
) return ; pos
= k
; int n
= pos1
; for ( int j
= k
; j
> pos1
; -- j
) { if ( arr
[ j
- 1 ] > arr
[ j
] ) { swap ( arr
[ j
- 1 ] , arr
[ j
] ) ; n
= j
- 1 ; flag
= false ; } } if ( flag
) return ; pos1
= n
; }
}
選擇排序
??選擇排序是一種簡單直觀的排序算法。
初始時設第一個元素為最大值，并記錄其下標為maxpos 從剩余未排序元素中繼續尋找最大元素，如果當前元素比下標為maxpos的元素大，將maxpos更新到當前位置 一次遍歷后，將下標為maxpos的元素與最后一個元素交換位置 以此類推，直到整個數組有序。
??注意：選擇排序與冒泡排序是區別的，冒泡排序通過依次交換相鄰兩個順序不合法的元素位置，從而將當前最大元素放到合適的位置，而選擇排序每遍歷一次都記住了當前最大元素的位置，最后僅需一次交換操作即可將其放到合適的位置。
直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
void slectSort ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; for ( int i
= 0 ; i
< size
- 1 ; ++ i
) { int maxPos
= 0 ; for ( int j
= 1 ; j
< size
- i
; ++ j
) { if ( arr
[ j
] > arr
[ maxPos
] ) maxPos
= j
; } if ( maxPos
!= size
- i
- 1 ) swap ( arr
[ maxPos
] , arr
[ size
- i
- 1 ] ) ; }
}
優化
void SlectSort ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; int begin
= 0 ; int end
= size
- 1 ; while ( begin
< end
) { int minPos
= begin
; int maxPos
= begin
; int index
= begin
+ 1 ; while ( index
<= end
) { if ( arr
[ minPos
] > arr
[ index
] ) minPos
= index
; if ( arr
[ maxPos
] < arr
[ index
] ) maxPos
= index
; ++ index
; } if ( maxPos
!= end
) swap ( arr
[ maxPos
] , arr
[ end
] ) ; if ( minPos
== end
) minPos
= maxPos
; if ( minPos
!= begin
) swap ( arr
[ begin
] , arr
[ minPos
] ) ; ++ begin
; -- end
; }
}
??上面代碼標記的一小段代碼是為了防止minpos在最大值要插入的位置。比如序列（2，15，4，1）這時候的maxpos為1，minpos為3，調整過最大值后，序列就成了（2，1，4，15），這時候的minpos還是3，如果直接進行最小值交換，就恢復到之前的位置了，所以要加上這段判斷代碼。這樣如果最小值在最大值要交換的位置，最大值交換后要將最小值的位置更新到maxpos的位置。
插入排序
??直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。實際中我們玩撲克牌時，就用了插入排序的思想
元素集合越接近有序，直接插入排序算法的時間效率越高
void InsertSort ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; for ( int i
= 1 ; i
< size
; ++ i
) { int key
= arr
[ i
] ; int end
= i
- 1 ; while ( end
>= 0 && arr
[ end
] > key
) { arr
[ end
+ 1 ] = arr
[ end
] ; end
-- ; } arr
[ end
+ 1 ] = key
; }
}
優化
void InsertSort1 ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; for ( int i
= 1 ; i
< size
; ++ i
) { int key
= arr
[ i
] ; int right
= i
- 1 ; int left
= 0 ; if ( arr
[ right
] > key
) { while ( left
<= right
) { int mid
= left
+ ( ( right
- left
) >> 1 ) ; if ( arr
[ mid
] < key
) left
= mid
+ 1 ; else right
= mid
- 1 ; } } int end
= i
- 1 ; while ( end
>= left
) { arr
[ end
+ 1 ] = arr
[ end
] ; -- end
; } arr
[ end
+ 1 ] = key
; }
}
希爾排序
??希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。
希爾排序是對直接插入排序的優化。
void ShellSort ( vector
< int > & arr
)
{ int size
= arr
. size ( ) ; int gap
= size
; while ( gap
> 0 ) { gap
= gap
/ 3 + 1 ; for ( int i
= gap
; i
< size
; ++ i
) { int key
= arr
[ i
] ; int end
= i
- gap
; while ( end
>= 0 && arr
[ end
] > key
) { arr
[ end
+ gap
] = arr
[ end
] ; end
- = gap
; } arr
[ end
+ gap
] = key
; } if ( gap
== 1 ) break ; }
}
快速排序
??快速排序快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
普通快排：
int Partion ( vector
< int > & arr
, int left
, int right
)
{ int key
= arr
[ right
- 1 ] ; int begin
= 0 ; int end
= right
- 1 ; while ( begin
< end
) { while ( begin
< end
&& arr
[ begin
] <= key
) begin
++ ; while ( begin
< end
&& arr
[ end
] >= key
) end
-- ; if ( begin
!= end
) swap ( arr
[ begin
] , arr
[ end
] ) ; } if ( begin
!= right
- 1 ) swap ( arr
[ begin
] , arr
[ right
- 1 ] ) ; return begin
;
}
優化一：挖坑法
int Partion1 ( vector
< int > & arr
, int left
, int right
)
{ int end
= right
- 1 ; int begin
= left
; int key
= arr
[ right
- 1 ] ; while ( begin
< end
) { while ( begin
< end
&& arr
[ begin
] <= key
) begin
++ ; if ( begin
< end
) { arr
[ end
] = arr
[ begin
] ; end
-- ; } while ( begin
< end
&& arr
[ end
] >= key
) end
-- ; if ( begin
< end
) { arr
[ begin
] = arr
[ end
] ; begin
++ ; } } arr
[ begin
] = key
; return begin
;
}
int Partion2 ( vector
< int > & arr
, int left
, int right
)
{ int key
= arr
[ right
- 1 ] ; int cur
= left
; int pre
= cur
- 1 ; while ( cur
< right
) { if ( arr
[ cur
] < key
&& ++ pre
!= cur
) { swap ( arr
[ pre
] , arr
[ cur
] ) ; } cur
++ ; } if ( ++ pre
!= right
- 1 ) swap ( arr
[ pre
] , arr
[ right
- 1 ] ) ; return pre
;
}
int MidNum ( vector
< int > & arr
, int left
, int right
)
{ int mid
= left
+ ( ( right
- left
) >> 1 ) ; if ( arr
[ left
] > arr
[ right
] ) { if ( arr
[ mid
] > arr
[ left
] ) mid
= left
; if ( arr
[ mid
] < arr
[ right
] ) mid
= right
; } else { if ( arr
[ mid
] < arr
[ left
] ) mid
= left
; if ( arr
[ mid
] > arr
[ right
] ) mid
= right
; } return mid
;
}
int Partion3 ( vector
< int > & arr
, int left
, int right
)
{ int end
= right
- 1 ; int begin
= left
; int mid
= MidNum ( arr
, left
, end
) ; swap ( arr
[ mid
] , arr
[ right
- 1 ] ) ; int key
= arr
[ right
- 1 ] ; while ( begin
< end
) { while ( begin
< end
&& arr
[ begin
] <= key
) begin
++ ; if ( begin
< end
) { arr
[ end
] = arr
[ begin
] ; end
-- ; } while ( begin
< end
&& arr
[ end
] >= key
) end
-- ; if ( begin
< end
) { arr
[ begin
] = arr
[ end
] ; begin
++ ; } } arr
[ begin
] = key
; return begin
;
}
void QuickSort ( vector
< int > & arr
, int left
, int right
)
{ if ( right
- left
> 1 ) { int key
= Partion3 ( arr
, left
, right
) ; QuickSort ( arr
, left
, key
) ; QuickSort ( arr
, key
+ 1 , right
) ; }
}
void QuickSortNor ( vector
< int > & arr
)
{ int right
= arr
. size ( ) ; int left
= 0 ; stack
< int > s
; s
. push ( right
) ; s
. push ( left
) ; while ( ! s
. empty ( ) ) { left
= s
. top ( ) ; s
. pop ( ) ; right
= s
. top ( ) ; s
. pop ( ) ; if ( right
- left
> 1 ) { int key
= Partion3 ( arr
, left
, right
) ; s
. push ( right
) ; s
. push ( key
+ 1 ) ; s
. push ( key
) ; s
. push ( left
) ; } } }
堆排序
??堆排序就是利用堆（堆的詳細介紹）這種數據結構進行排序的算法，堆排序屬于選擇排序
時間復雜度：O(nlogn)
typedef struct Heap
{ HPData
* _array
; int _size
; int _capacity
;
} Heap
; void HeapAdjust ( HPData
* array
, int size
, int root
)
{ int child
= root
* 2 + 1 ; while ( child
< size
) { if ( child
+ 1 < size
&& array
[ child
] < array
[ child
+ 1 ] ) child
+ = 1 ; if ( array
[ child
] > array
[ root
] ) { swap ( array
[ child
] , array
[ root
] ) ; root
= child
; child
= root
* 2 + 1 ; } else return ; }
} void HeapSort ( HPData
* array
, int size
)
{ int root
= ( size
- 2 ) >> 1 ; for ( ; root
>= 0 ; -- root
) HeapAdjust ( array
, size
, root
) ; int end
= size
- 1 ; while ( end
) { swap ( array
[ 0 ] , array
[ end
] ) ; HeapAdjust ( array
, end
, 0 ) ; end
-- ; }
}
歸并排序
??歸并排序是簡歷在歸并操作上的一中有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列。顯示每個子序列有序，再使子序列段間有序。若兩個有序列表合并成一個有序列表，陳偉二路歸并。
歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
void _MergeData ( vector
< int > & arr
, int left
, int mid
, int right
, vector
< int > & temp
)
{ int begin1
= left
; int end1
= mid
; int begin2
= mid
; int end2
= right
; int index
= left
; while ( begin1
< end1
&& begin2
< end2
) { if ( arr
[ begin1
] < arr
[ begin2
] ) temp
[ index
++ ] = arr
[ begin1
++ ] ; else temp
[ index
++ ] = arr
[ begin2
++ ] ; } while ( begin1
< end1
) temp
[ index
++ ] = arr
[ begin1
++ ] ; while ( begin2
< end2
) temp
[ index
++ ] = arr
[ begin2
++ ] ; } void _MergeSort ( vector
< int > & arr
, int left
, int right
, vector
< int > & temp
)
{ if ( ( right
- left
) > 1 ) { int mid
= left
+ ( ( right
- left
) >> 1 ) ; _MergeSort ( arr
, left
, mid
, temp
) ; _MergeSort ( arr
, mid
, right
, temp
) ; _MergeData ( arr
, left
, mid
, right
, temp
) ; copy ( temp
. begin ( ) + left
, temp
. begin ( ) + right
, arr
. begin ( ) + left
) ; }
}
總結
以上是生活随笔 為你收集整理的排序（冒泡、选择、插入、希尔、快排、堆排、归并） 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
