排序算法
冒泡排序
- (void)bubbleSort:(NSMutableArray <NSNumber *>*)ary {
NSLog(@"\n排序前\n");
[self printAry:ary];
for (int i = 0 ; i < ary.count ; i ++) {
for (int j = 0; j < ary.count - i - 1; j ++) {
if ([ary[j] intValue] > [ary[j + 1] intValue]) {
[ary exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
NSLog(@"\n排序后\n");
[self printAry:ary];
}
- (void)bubbleSort:(NSMutableArray <NSNumber *>*)ary {
NSLog(@"\n排序前\n");
[self printAry:ary];
for (int i = 0; i < ary.count ; i++) {
for (int j = ary.count - 2; j >= i; j--) {
if ([ary[j] intValue] > [ary[j + 1] intValue]) {
[ary exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
[self printAry:ary];
}
}
}
NSLog(@"\n\n\n\n排序后\n");
[self printAry:ary];
}
func bubbleSort(nums: inout [Int]) {
for i in nums.indices.dropFirst().reversed() {
for j in 0..<i {
if nums[j] > nums[j + 1] {
nums.swapAt(j, j + 1)
}
}
}
}
选择排序
- (void)selectSort:(NSMutableArray <NSNumber *>*)ary {
NSInteger idx;
for (NSInteger i = 0 ; i < ary.count - 1; i++) {
idx = i;
for (NSInteger j = i + 1; j < ary.count ; j++) {
if (ary[idx].intValue > ary[j].intValue) {
idx = j;
}
}
if (idx != i) {
[ary exchangeObjectAtIndex:i withObjectAtIndex:idx];
}
}
}
func selectionSort(ary: inout [Int]) {
for i in 0..<(ary.count - 1){
var minIndex = i
for j in (i+1)..<ary.count {
if ary[j] < ary[minIndex] {
minIndex = j
}
}
//(ary[i], ary[minIndex]) = (ary[minIndex], ary[i])
ary.swapAt(i, minIndex)
}
}
func selectionSort(ary: inout [Int]) {
for i in ary.indices.dropLast() {
var minIndex = i
for j in ary.indices.dropFirst(i + 1) {
minIndex = ary[j] < ary[minIndex] ? j : minIndex
}
(ary[i], ary[minIndex]) = (ary[minIndex], ary[i])
}
}
快速排序
- (void)quickSort:(NSMutableArray <NSNumber *>*)ary
leftIdx:(NSInteger)leftIdx
rightIdx:(NSInteger)rightIdx {
if (leftIdx >= rightIdx) {
return;
}
NSInteger i = leftIdx;
NSInteger j = rightIdx;
NSInteger key = ary[i].intValue;
while (i < j) {
while (i < j && ary[j].intValue >= key) {
j--;
}
ary[i] = ary[j];
while (i < j && ary[i].intValue <= key) {
i++;
}
ary[j] = ary[i];
}
ary[i] = @(key);
[self quickSort:ary leftIdx:leftIdx rightIdx:i-1];
[self quickSort:ary leftIdx:i+1 rightIdx:rightIdx];
}
func partition(nums: inout [Int], left: Int, right: Int) -> Int {
var i = left
var j = right
while i < j {
while i < j, nums[j] >= nums[left] {
j -= 1
}
while i < j, nums[i] <= nums[left] {
i += 1
}
nums.swapAt(i, j)
}
nums.swapAt(i, left)
return i
}
func quickSort(nums: inout [Int], left: Int, right: Int) {
if left >= right {
return
}
let pivot = partition(nums: &nums, left: left, right: right)
quickSort(nums: &nums, left: left, right: pivot - 1)
quickSort(nums: &nums, left: pivot + 1, right: right)
}
插入
- (void)straightInsertionSortWithNumbers:(NSMutableArray *)numbers {
for (int i = 1; i < numbers.count; i++) {
if ([numbers[i - 1] intValue] > [numbers[i] intValue]) {//前面一位大于后面一位
int temp = [numbers[i] intValue];
for (int j = i - 1; j >= 0 && [numbers[j] intValue] > temp; j--) {
[numbers exchangeObjectAtIndex:j + 1 withObjectAtIndex:j];
}
}
}
NSLog(@"%@",numbers);
}
func insertionSort(nums: inout [Int]) {
for i in nums.indices.dropFirst() {
let base = nums[i]
var j = i - 1
while j >= 0, nums[j] > base {
nums[j + 1] = nums[j]
j -= 1
}
nums[j + 1] = base
}
}
归并排序
func mergeSort(nums: [Int]) -> [Int] {
let length = nums.count
if length <= 1 {
return nums
}
let middle = length / 2
let leftAry = mergeSort(nums: Array(nums[0..<middle]))
let rightAry = mergeSort(nums: Array(nums[middle..<length]))
var result = [Int]()
var leftIndex = 0
var rightIndex = 0
while leftIndex < leftAry.count && rightIndex < rightAry.count {
if leftAry[leftIndex] < rightAry[rightIndex] {
result.append(leftAry[leftIndex])
leftIndex += 1
} else {
result.append(rightAry[rightIndex])
rightIndex += 1
}
}
while leftIndex < leftAry.count {
result.append(leftAry[leftIndex])
leftIndex += 1
}
while rightIndex < rightAry.count {
result.append(rightAry[rightIndex])
rightIndex += 1
}
print(result)
return result
}
二分查找
- (NSInteger)halfSearch:(NSMutableArray <NSNumber *>*)ary
target:(NSNumber *)target {
NSInteger low = 0;
NSInteger high = ary.count - 1;
while (low <= high) {
NSInteger mid = (low + high) / 2;
if (ary[mid].intValue < target.intValue) {
low = mid + 1;
} else if (ary[mid].intValue > target.intValue) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
汉诺塔问题
/* 移动一个圆盘 */
func move(src: inout [Int], tar: inout [Int]) {
// 从 src 顶部拿出一个圆盘
let pan = src.popLast()!
// 将圆盘放入 tar 顶部
tar.append(pan)
}
/* 求解汉诺塔问题 f(i) */
func dfs(i: Int, src: inout [Int], buf: inout [Int], tar: inout [Int]) {
// 若 src 只剩下一个圆盘，则直接将其移到 tar
if i == 1 {
move(src: &src, tar: &tar)
return
}
// 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
dfs(i: i - 1, src: &src, buf: &tar, tar: &buf)
// 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
move(src: &src, tar: &tar)
// 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
dfs(i: i - 1, src: &buf, buf: &src, tar: &tar)
}
/* 求解汉诺塔问题 */
func solveHanota(A: inout [Int], B: inout [Int], C: inout [Int]) {
let n = A.count
// 列表尾部是柱子顶部
// 将 src 顶部 n 个圆盘借助 B 移到 C
dfs(i: n, src: &A, buf: &B, tar: &C)
}
var A = [1,2,3,4,5]
var B = [Int]()
var C = [Int]()
solveHanota(A: &A, B: &B, C: &C)
func hanoiTower(disksNumber: Int, from: String, via: String, to: String) {
if disksNumber == 1 {
print("Move disk 1 from \(from) to \(to)")
} else {
hanoiTower(disksNumber: disksNumber - 1, from: from, via: to, to: via)
print("Move disk \(disksNumber) from \(from) to \(to)")
hanoiTower(disksNumber: disksNumber - 1, from: via, via: from, to: to)
}
}
// 使用函数
let numberOfDisks = 3
hanoiTower(disksNumber: numberOfDisks, from: "A", via: "B", to: "C")
