一、冒泡排序
- 最好情况下，数组已经是有序的，时间复杂度 O(n)
- 最坏和平均时间复杂度 O(n^2)
- 空间复杂度 O(1)
- 稳定的排序算法
func sortWithBubble(nums : inout [Int]) -> [Int] {
for i in 0..<nums.count {
var isSorted = false;
for j in 0..<nums.count - i - 1 {
if nums[j] > nums[j+1] {
nums.swapAt(j+1, j)
isSorted = true;
}
}
if isSorted == false {
break;
}
}
return nums;
}
二、插入排序
- 最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为 O(n)
- 最坏和平均时间复杂度 O(n^2)
- 空间复杂度 O(1)
- 稳定的排序算法
func sortWithInsertion(nums: inout [Int]) -> [Int] {
for i in 1..<nums.count {
var j = i;
while j > 0 && nums[j] < nums[j - 1] {
nums.swapAt(j - 1, j)
j -= 1;
}
}
return nums;
}
三、选择排序
- 无论如何都要完整地执行内外两重循环，故最好、最差和平均时间复杂度都是O(n2)
- 空间复杂度 O(1)
- 不稳定的排序算法
func sortWithSelect(nums: inout Array<Int>) -> Array<Int> {
for i in 0..<nums.count {
var index = i;
for j in i..<nums.count {
if nums[index] > nums[j] {
index = j;
}
}
nums.swapAt(i, index);
}
return nums;
}
四、快速排序
- 它的最好和平均实际复杂度为O(nlogn)
- 最坏时间复杂度为O(n^2)
- 快排算法本身没有用到额外的空间，可以说需要的空间为O(1)，对于递归实现，也可以说需要的空间是O(n)，因为在递归调用时有栈的开销，当然最坏情况是O(n)，平均情况是O(logn)
- 不稳定的排序算法
// 快速排序
func quickSort(nums: inout Array<Int>,left: Int,right: Int) -> Array<Int> {
if left < right {
let mid = partition(nums: &nums, left: left, right: right);
print(mid);
quickSort(nums: &nums, left: left, right: mid - 1);
quickSort(nums: &nums, left: mid + 1, right: right);
}
return nums;
}
func partition(nums: inout Array<Int>, left: Int, right: Int) -> Int {
var mid = left;
let key = nums[left];
for i in left...right {
if nums[i] < key {
mid += 1;
if mid != i {
nums.swapAt(mid, i);
}
}
}
nums.swapAt(left, mid);
return mid;
}
五、归并排序
- 无论最好还是最坏均为 O(nlogn)
- 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)
- 是一种稳定的排序算法
// 自上而下
func mergeSort(nums: inout Array<Int>) -> [Int] {
guard nums.count > 1 else {
return nums;
}
let low = 0;
let hig = nums.count;
let mid = low + (hig - low) / 2;
var left = Array(nums[low..<mid]);
var right = Array(nums[mid..<hig]);
let leftArray = mergeSort(nums: &left)
let rightArray = mergeSort(nums: &right)
return merge(left: leftArray, right: rightArray);
}
func merge(left: [Int], right: [Int]) -> [Int] {
var leftIndex = 0;
var rightIndex = 0;
var result = [Int]();
while leftIndex < left.count && rightIndex < right.count {
if left[leftIndex] < right[rightIndex] {
result.append(left[leftIndex]);
leftIndex += 1;
} else if left[leftIndex] > right[rightIndex] {
result.append(right[rightIndex]);
rightIndex += 1;
} else {
result.append(left[leftIndex])
leftIndex += 1
result.append(right[rightIndex])
rightIndex += 1
}
}
while leftIndex < left.count {
result.append(left[leftIndex]);
leftIndex += 1;
}
while rightIndex < right.count {
result.append(right[rightIndex]);
rightIndex += 1;
}
return result;
}
// 自下而上
func mergeBottomToTop(nums: inout Array<Int>) {
var step = 1;
while step < nums.count {
let offSet = step + step;
var index = 0;
while index < nums.count {
mergeBottomSortHelper(nums: &nums, head1: index, head2: min(index + step, nums.count - 1), tail2: min(index + offSet - 1, nums.count - 1))
index += offSet;
}
// 倍进枚举步长 1 2 4 8。。。
step <<= 1;
}
}
// 区间【head1 head2 - 1】 和 【head2 tail2】 都是排好序的，现在需要合并
func mergeBottomSortHelper(nums: inout [Int], head1: Int, head2: Int, tail2: Int) {
var head1 = head1, head2 = head2, tail2 = tail2;
var tail1 = head2 - 1, index = 0, len = tail2 - head1 + 1, start = head1;
print(head1,tail1,head2,tail2)
var temp = [Int](repeating: 0, count: len);
while head1 <= tail1 || head2 <= tail2 {
if head1 > tail1 {
temp[index] = nums[head2];
index += 1;
head2 += 1;
} else if head2 > tail2 {
temp[index] = nums[head1];
index += 1;
head1 += 1;
} else {
if nums[head1] <= nums[head2] {
temp[index] = nums[head1];
index += 1;
head1 += 1;
} else {
temp[index] = nums[head2];
index += 1;
head2 += 1;
}
}
}
for i in 0..<len {
nums[start + i] = temp[i];
}
}
