冒泡排序（Bubble Sort）
演算法描述：通過不斷地交換相鄰兩個元素，把最大的元素移到陣列的最后面，然后不斷縮小排序范圍，直到整個陣列有序，
演算法步驟：
- 遍歷整個待排序的陣列，
- 比較相鄰的兩個元素，
- 如果前面的元素比后面的元素大，就交換它們
- 重復以上步驟，直到整個陣列有序，
偽代碼：
procedure bubbleSort(array A)
n := length(A)
repeat
swapped := false
for i from 1 to n-1 do
if A[i] > A[i+1] then
swap(A[i], A[i+1])
swapped := true
end if
end for
n := n - 1
until not swapped
end procedure選擇排序（Selection Sort）
演算法描述：對于一組待排序的元素，先找到最小元素，然后把它放到第一位，接著再找到次小元素，放到第二位，依次類推，直到所有的排序作業都已經完成，
演算法步驟：
- 找到陣列中最小元素并記錄其位置，
- 把最小元素放在陣列的起始位置，
- 從下一個元素開始，重復以上步驟，直到整個陣列有序，
偽代碼：
procedure selectionSort(array A)
n := length(A)
for i from 1 to n-1 do
minIndex := i
for j from i+1 to n do
if A[j] < A[minIndex] then
minIndex := j
end if
end for
swap(A[i], A[minIndex])
end for
end procedure插入排序（Insertion Sort）
演算法描述：將一個記錄插入到已經排好的有序序列中，從而得到一個新的，記錄數增加1的有序序列，
演算法步驟：
- 從第一個元素開始，該元素可以認為已經被排序，
- 取出下一個元素，在已經排序的元素序列中從后向前掃描，
- 如果被掃描的元素大于新元素，將該元素往右移動一個位置，
- 重復步驟3，直到找到已排序的元素小于或等于新元素的位置，
- 將新元素插入到該位置后，
- 重復以上步驟，直到整個陣列有序，
偽代碼：
procedure insertionSort(array A)
n := length(A)
for i from 2 to n do
key := A[i]
j := i - 1
while j > 0 and A[j] > key do
A[j+1] := A[j]
j := j - 1
end while
A[j+1] := key
end for
end procedure希爾排序（Shell Sort）
演算法描述：將原始陣列按照一定的間隔分為若干子序列，然后對每個子序列進行插入排序，直到整個陣列排序完成，
演算法步驟：
- 確定分組間隔gap的大小（最開始可以設為陣列長度的一半），
- 按照gap的大小將原始陣列分為若干個子序列，
- 對每個子序列進行插入排序，
- 縮小gap的大小，重復以上步驟，直到gap為1時，整個陣列排序完成，
偽代碼：
procedure shellSort(array A)
n := length(A)
gap := n / 2
while gap > 0 do
for i from gap to n-1 do
temp := A[i]
j := i
while j >= gap and A[j-gap] > temp do
A[j] := A[j-gap]
j := j - gap
end while
A[j] := temp
end for
gap := gap / 2
end while
end procedure歸并排序（Merge Sort）
演算法描述：將原始陣列分成若干個較小的子陣列，對每個子陣列進行排序，然后再將排好序的子陣列合并成一個大的有序陣列，
演算法步驟：
- 把長度為n的陣列分成兩個長度為n/2的子陣列，
- 對這兩個子陣列分別進行歸并排序，
- 將排好序的兩個子陣列合并成一個大的有序陣列，
偽代碼：
procedure mergeSort(array A)
n := length(A)
if n > 1 then
mid := n / 2
left := A[1..mid]
right := A[mid+1..n]
mergeSort(left)
mergeSort(right)
merge(left, right, A)
end if
end procedure
procedure merge(left, right, A)
i := 1
j := 1
k := 1
while i <= length(left) and j <= length(right) do
if left[i] <= right[j] then
A[k] := left[i]
i := i + 1
else
A[k] := right[j]
j := j + 1
end if
k := k + 1
end while
while i <= length(left) do
A[k] := left[i]
i := i + 1
k := k + 1
end while
while j <= length(right) do
A[k] := right[j]
j := j + 1
k := k + 1
end while
end procedure快速排序（Quick Sort）
演算法描述：將原始陣列分為兩個子陣列，其中一個子陣列的所有元素都比另一個子陣列的元素小，再遞回地對兩個子陣列進行快速排序，直到整個陣列有序，
演算法步驟：
- 從陣列中取一個基準元素（通常選擇第一個元素），
- 把陣列中小于基準元素的元素放在基準元素左邊，大于基準元素的元素放在基準元素右邊，
- 對基準元素左右兩個子集遞回地進行快速排序，
偽代碼：
procedure quickSort(array A, left, right)
if left < right then
pivot := partition(A, left, right)
quickSort(A, left, pivot-1)
quickSort(A, pivot+1, right)
end if
end procedure
function partition(A, left, right)
pivot := A[left]
i := left + 1
j := right
while true do
while i <= j and A[i] < pivot do
i := i + 1
end while
while i <= j and A[j] > pivot do
j := j - 1
end while
if i <= j then
swap(A[i], A[j])
else
break
end if
end while
swap(A[left], A[j])
return j
end function堆排序（Heap Sort）
演算法描述：將原始陣列看成一個完全二叉樹，并將其調整為大根堆，然后將根節點（即最大值）與最后一個節點交換位置，縮小排序范圍，重復以上步驟，直到整個陣列有序，
演算法步驟：
- 將原始陣列調整為大根堆，
- 將堆頂元素（即最大元素）與最后一個葉子節點交換位置，
- 對減少一個元素的堆進行調整，使其重新成為一個大根堆，
- 重復以上步驟，直到整個陣列有序，
偽代碼：
procedure maxHeapify(A, i, heapSize)
left := 2 * i
right := 2 * i + 1
largest := i
if left <= heapSize and A[left] > A[largest] then
largest := left
end if
if right <= heapSize and A[right] > A[largest] then
largest := right
end if
if largest != i then
swap(A[i], A[largest])
maxHeapify(A, largest, heapSize)
end if
end procedure
procedure buildMaxHeap(A, heapSize)
for i from floor(heapSize/2) down to 1 do
maxHeapify(A, i, heapSize)
end for
end procedure
procedure heapSort(A)
heapSize := length(A)
buildMaxHeap(A, heapSize)
for i from heapSize downto 2 do
swap(A[1], A[i])
heapSize := heapSize - 1
maxHeapify(A, 1, heapSize)
end for
end procedure
end function計數排序（Counting Sort）
演算法描述：對于有限的數列，使用一個全新的數列記錄它們的出現次數，再根據出現次數將原始數列排序，
演算法步驟：
- 找到原始陣列的最大值max，
- 初始化一個長度為max的計數陣列C，對每個元素統計它出現的次數，
- 對計數陣列C進行累加，得到C的新陣列D，
- 從右到左遍歷原始陣列，根據元素在計數陣列D中的位置，將元素插入到新陣列R中的合適位置，
- 回傳新陣列R，
偽代碼：
procedure countingSort(A)
max := 0
for i from 1 to length(A) do
if A[i] > max then
max := A[i]
end if
end for
C := array(0..max, 0)
for i from 1 to length(A) do
C[A[i]] := C[A[i]] + 1
end for
D := array(0..max, 0)
for i from 1 to max do
D[i] := D[i-1] + C[i]
end for
R := array(1..length(A), 0)
for i from length(A) downto 1 do
R[D[A[i]]] := A[i]
D[A[i]] := D[A[i]] - 1
end for
return R
end procedure桶排序（Bucket Sort）
演算法描述：將原始陣列分為若干個桶，每個桶的元素值范圍相同，再對每個桶里的元素進行排序，將所有桶中的元素按順序依次排列在一起，
演算法步驟：
- 初始化若干個桶，桶的數量等于元素范圍的個數，
- 遍歷原始陣列中的每個元素，將元素放入相應的桶中，
- 對每個桶中的元素進行插入排序，使得每個桶內的元素有序，
- 將所有桶中的元素按順序依次排列在一起，
偽代碼：
procedure bucketSort(A)
n := length(A)
buckets := array(length(A))
for i from 1 to n do
bucketIndex := ceil(A[i] * n / max(A))
buckets[bucketIndex] := append(buckets[bucketIndex], A[i])
end for
for i from 1 to length(buckets) do
insertionSort(buckets[i])
end for
R := concatenate all buckets
return R
end procedure基數排序（Radix Sort）
演算法描述：將原始陣列按照數位進行比較和排序，先比較最低位，然后依次向上比較，直到比較完最高位，
演算法步驟：
- 從最低位開始，按照數位進行比較
- 對比較之后的元素按順序排列，
- 將已經排好序的元素從原始陣列中洗掉，并將它們按照排序順序依次插入到新的陣列中，
- 重復以上步驟，直到處理完最高位，
偽代碼：
procedure radixSort(A)
maxDigit := getMaxDigit(A)
for i from 1 to maxDigit do
buckets := array(0..9, empty array)
for j from 1 to length(A) do
digit := getDigit(A[j], i)
buckets[digit] := append(buckets[digit], A[j])
end for
A := concatenate all buckets
end for
return A
end procedure
function getMaxDigit(A)
max := 0
for i from 1 to length(A) do
if A[i] > max then
max := A[i]
end if
end for
return length(toString(max))
end function
function getDigit(num, i)
return mod(floor(num / power(10, i-1)), 10)
end function在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555511.html
標籤：其他
上一篇：LINUX LAMP架構
下一篇：返回列表