iOS快速排序

释放双眼,带上耳机,听听看~!

1、算法描述:

快速排序(Quicksort)是对冒泡排序的一种改进。

2、解答思路:

它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

3、实现:

Swift

class QuickSort {
//找到分割的index
func partition(array: inout [Int], left : Int, right : Int) -> Int {
var low = left
var high = right
let temp = array[low]
while low < high {
while low < high && array[high] >= temp {
high -= 1
}
array[low] = array[high]
while low < high && array[low] <= temp {
low += 1
}
array[high] = array[low]
}
array[low] = temp
print(array)
return low
}
//递归
func quickSort(array : inout [Int], left : Int , right : Int){
if left < right {
let mid = partition(array: &array, left: left, right: right)
quickSort(array: &array, left: left, right: mid - 1)
quickSort(array: &array, left: mid + 1, right: right)
}
}
}
let test = QuickSort()
var array  = [Int](repeating: 0, count: 6)
for index in 0..<6 {
array[index] = Int(arc4random_uniform(7)) + Int(arc4random_uniform(2)) + 1
}
test.quickSort(array : &array, left: 0, right: array.count - 1)
print(array)

C语言

void quickSort(int array[], int left, int right) {
if (left>=right) {
return;
}
int low = left;
int high = right;
int temp = array[low];
while (low < high) {
while (low < high && temp <= array[high]) {
high --;
}
array[low] = array[high];
while (low < high && temp >= array[low]) {
low ++;
}
array[high] = array[low];
}
array[low] = temp;
quickSort(array, left, low - 1);
quickSort(array, low + 1, right);
}

4、分析:

1)、时间复杂度:

时间复杂度为O(nlogn),是一种比较快的排序方式。

2)、空间复杂度:

和冒泡排序一样,需要额外空间为常量级,故空间复杂度为O(1)。

3)、算法稳定性:

假设现有数据:[5, 3, 8, 3, 4,10, 3, 11],这里存在3个3分别用3a,3b,3c表示这三个三。
第一次交换元素,得到:[4, 3a, 3c, 3b, 4, 10, 8, 11 ],原序3b在3c前面,现在3c在3b前面,交换了位置,所以该算法不是稳定算法

人已赞赏
iOS文章

iOS 蓝牙开发(框架集成和数据交互)

2020-1-14 15:20:10

iOS文章

iOS冒泡排序

2020-1-14 18:44:08

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索