算法描述:通过不断地交换相邻两个元素,把最大的元素移到数组的最后面,然后不断缩小排序范围,直到整个数组有序。
算法步骤:
伪代码:
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
算法描述:对于一组待排序的元素,先找到最小元素,然后把它放到第一位,接着再找到次小元素,放到第二位,依次类推,直到所有的排序工作都已经完成。
算法步骤:
伪代码:
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
算法描述:将一个记录插入到已经排好的有序序列中,从而得到一个新的,记录数增加1的有序序列。
算法步骤:
伪代码:
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
算法描述:将原始数组按照一定的间隔分为若干子序列,然后对每个子序列进行插入排序,直到整个数组排序完成。
算法步骤:
伪代码:
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
算法描述:将原始数组分成若干个较小的子数组,对每个子数组进行排序,然后再将排好序的子数组合并成一个大的有序数组。
算法步骤:
伪代码:
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
算法描述:将原始数组分为两个子数组,其中一个子数组的所有元素都比另一个子数组的元素小,再递归地对两个子数组进行快速排序,直到整个数组有序。
算法步骤:
伪代码:
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
算法描述:将原始数组看成一个完全二叉树,并将其调整为大根堆,然后将根节点(即最大值)与最后一个节点交换位置,缩小排序范围,重复以上步骤,直到整个数组有序。
算法步骤:
伪代码:
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
算法描述:对于有限的数列,使用一个全新的数列记录它们的出现次数,再根据出现次数将原始数列排序。
算法步骤:
伪代码:
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
算法描述:将原始数组分为若干个桶,每个桶的元素值范围相同,再对每个桶里的元素进行排序,将所有桶中的元素按顺序依次排列在一起。
算法步骤:
伪代码:
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
算法描述:将原始数组按照数位进行比较和排序,先比较最低位,然后依次向上比较,直到比较完最高位。
算法步骤:
伪代码:
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