Python搜索Jira：调整搜索顺序的实用方法

搜索

顺序查找

顺序查找：在python list中，数据项存储位置称为下标（index），通过下标，我们就可以按照顺序来访问和查找数据项

无序表的循序排序

def SequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos += 1
    return found


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
print(SequentialSearch(testlist, 3))1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

顺序查找的算法复杂度是O(n)

无序表循序排序搜索的比对

Case	Bset Case	Worst Case	Average Case
item is present	1	n	n/2
item is not present	n	n	n

有序表的循序排序

def orderSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False

    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos += 1
    return found


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(orderSequentialSearch(testlist, 3))1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

顺序查找的算法复杂度是O(n)

有序表循序排序搜索的比对

Case	Bset Case	Worst Case	Average Case
item is present	1	n	n/2
item is not present	1	n	n/2

二分查找

二分查找体现解决问题典型策略：分而治之

将问题分为若干更小规模的部分
通过解决每一个小规模部分问题，并将结果汇总得到原问题的解

def BinarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(BinarySearch(testlist, 17))1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

二分法也适用递归算法来实现

def BinarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return BinarySearch(alist[:midpoint], item)
            else:
                return BinarySearch(alist[midpoint+1:], item)


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(BinarySearch(testlist, 14))1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

这个递归调用使用列表切片，而切片操作的复杂度是O(k)，这样会使整个算法的时间复杂度稍有增加

项数	分割次数
1	n/2
2	n/4
…	…
i	n/2^i

python 搜索JIRA python 搜索顺序调整_python 搜索JIRA

所以二分查找的算法复杂度是O(log(n))

虽然二分查找在时间复杂复杂度上优于顺序查找，但也要考虑到对数据项进行排序的开销

排序

可视化： https://visualgo.net/zh

python 搜索JIRA python 搜索顺序调整_后端_02

主流的排序算法可以分为3大类：

时间复杂度为O(n²)的排序算法

冒泡排序
选择排序
插入排序
希尔排序（希尔排序比较特殊，它的性能略优于O(n²)，但又比不上O(n log n)，姑且把它归入本类）

时间复杂度为O(n log n)的排序算法

归并排序
快速排序
堆排序

时间复杂度为线性的排序算法

计数排序
桶排序
基数排序

十大经典排序算法总结

冒泡排序

时间复杂度：O(n²)
空间复杂度：O(1)

冒泡排序：对一个列表多次重复遍历，它要比较相邻的两项，并且交换顺序排错的项

python 搜索JIRA python 搜索顺序调整_python 搜索JIRA_03

算法过程总需要n-1趟，随着趟数的增加，比对次数逐步从n-1减少到1，并包括可能发生的数据项交换

对比次数是 1 ~ n-1 的累加：1/2 n²-1/2 n

比对的时间复杂度是O(n²)

最好：列表在排序前已经有序，交换次数是0
最差：每次对比都要进行交换，交换次数等于对比次数

冒泡排序

python版本

def BubbleSort(alist):
    for passnum in range(len(alist)-1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
BubbleSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

js版本

function BubbleSort1(arr) {
    console.time('改进前冒泡排序耗时');
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    console.timeEnd('改进前冒泡排序耗时');
    return arr
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(BubbleSort1(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.

优势：无需任何额外的存储空间开销（顺序表、链表都适用）

冒泡排序：性能优化

通过监测每趟比对是否发生过交换，可以提前确定排序是否完成
我们在每一轮排序后，记录下最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了

短路冒泡排序

python版本

def BubbleSort2(alist):
    # 记录最后一次交换的位置
    last_exchange_index = 0
    # 无序数列的边界，每次比较只需要比到这里
    passnum = len(alist) - 1
    exchanges = True
    while passnum > 0 and exchanges:
        # 假定每一轮不需要进行交换
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                # 有元素交换，所以不是有序的，需要进行交换
                exchanges = True
                # 把无序数列的边界更新为最后一次交换元素的位置
                last_exchange_index = i
        passnum = last_exchange_index

testlist = [1, 2, 32, 8, 17, 19, 42, 13]
BubbleSort2(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

js版本

function BubbleSort2(arr) {
    console.time('改进后冒泡排序耗时');
    var i = arr.length - 1;
    var exchange = true;
    var pos = 0; //每趟开始时,无记录交换
    while (i > 0 && exchange) {
        exchange = false;
        for (var j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                exchange = true;
                pos = j; //记录交换的位置
            }
        }
        i = pos; //为下一趟排序作准备
    }

    console.timeEnd('改进后冒泡排序耗时');
    return arr;
}


var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(BubbleSort2(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

冒泡排序：鸡尾酒排序

冒泡排序算法每一轮都是从左到右，并进行单向的位置交换的

鸡尾酒排序的元素比较和交换过程是双向的

python版本

def BubbleSort3(alist):
    low = 0
    high = len(alist) - 1
    exchanges = True
    while high > low and exchanges:
        exchanges = False
        for i in range(low,high):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
                exchanges = True
        high -= 1
        for j in range(high,low,-1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
                exchanges = True
        low += 1

testlist = [1, 2, 32, 8, 17, 19, 42, 13]
BubbleSort3(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

js版本

function BubbleSort3(arr) {
    console.time('鸡尾酒_改进后冒泡排序耗时');
    var low = 0;
    var high = arr.length - 1;
    var j, tmp;
    while (low < high) {
        for (j = low; j < high; ++j) {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
        --high;
        for (j = high; j > low; --j) {
            if (arr[j] < arr[j - 1]) {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            }
        }
        ++low;
    }

    console.timeEnd('鸡尾酒_改进后冒泡排序耗时');
    return arr;
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(BubbleSort3(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

选择排序

时间复杂度：O(n²)
空间复杂度：O(1)

选择排序提高了冒泡排序的性能，它每遍历一次列表只交换一次数据，即进行一次遍历时找到数据的最大的项，完成遍历后，再把它交换到正确的位置

比对次数不变，还是O(n²)
交换次数减少为O(n)

python 搜索JIRA python 搜索顺序调整_python 搜索JIRA_04

python版本

def SelectionSort(alist):
    for fillslot in range(len(alist)-1, 0, -1):
        positionOfMax = 0
        for location in range(1, fillslot+1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        alist[fillslot], alist[positionOfMax] = alist[positionOfMax], alist[fillslot]


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
SelectionSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

js版本

function SelectionSort(arr) {
    console.time('选择排序耗时');
    var len = arr.length;
    var maxIndex, temp;
    for (var i = 0; i < len; i++) {
        maxIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[maxIndex]) {
                maxIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }

    console.timeEnd('选择排序耗时');
    return arr
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(SelectionSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

插入排序

时间复杂度：O(n²)
空间复杂度：O(1)

插入排序总是维持一个位置靠前的已排好的子表，然后每一个新的数据项被“插入”到前面的子表里，排好的子表增加一项（类似整理扑克牌）

python 搜索JIRA python 搜索顺序调整_python_05

算法复杂度仍是O(n²)

最好：列表已经排好序的时候，每趟仅需1次对比，总次数是O(n)
最差：每趟都与子列表中所有项进行比对，总比对次数与冒泡排序相同，数量级是O(n²)

由于移动操作仅包含1次赋值，是交换操作的 1/3，所以插入排序性会较好一些

插入排序

python版本

def InsertSort(alist):
    # index是新项的位置
    for index in range(1, len(alist)):
        currentValue = alist[index]
        # 把新项取出来后，index位置空出来了
        position = index
        # 从新项前面的位置倒着往前走，进行比对移动
        while position > 0 and alist[position-1] > currentValue:
            alist[position] = alist[position-1]
            position -= 1
        alist[position] = currentValue


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
InsertSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

js版本

function InsertionSort(arr) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {
        console.time('插入排序耗时');
        for (var i = 1; i < arr.length; i++) {
            var key = arr[i];
            var j = i;
            while (j > 0 && arr[j - 1] > key) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = key;
        }

        console.timeEnd('插入排序耗时');
        return arr
    } else {
        return 'arr is not an Array'
    }
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(InsertionSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

折半插入排序

待查找位置下标 [low, high]
每次跟中间元素对比 mid=(low+high)/2
根据对比结果，调整查找范围 (改变low或high)
x>arr[mid] -> low=mid+1
x<arr[mid] -> high=mid-1
反复查找，找到插入位置 high+1
挪到元素从last -> high+1
插入元素 x -> high+1

python版本

def InsertSort(alist):
    for index in range(1, len(alist)):
        low, high = 0, index-1
        currentValue = alist[index]
        # 用二分法找插入位置
        # high+1 就是插入位置
        while low <= high:
            mid = (low + high) // 2
            if currentValue <= alist[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # 挪动元素
        for j in range(index, high, -1):
            alist[j] = alist[j-1]
        # 插入元素
        alist[high+1] = currentValue

testlist = [1, 2, 32, 8, 17, 19, 42, 13]
InsertSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.

js版本

function InsertionSort(arr) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array') {
        console.time('二分插入排序耗时');
        for (var i = 1; i < arr.length; i++) {
            var key = arr[i], low = 0, high = i - 1;
            while (low <= high) {
                var middle = parseInt((high + low) / 2);
                if (key <= arr[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            for (var j = i; j > high; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high + 1] = key;
        }
        console.timeEnd('二分插入排序耗时');
        return arr
    } else {
        return 'arr is not an arr'
    }
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(InsertionSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

希尔排序

时间复杂度：O(n log n)
空间复杂度：O(1)

希尔排序（缩小间隔排序）它以插入排序为基础，将原来要排序的列表划分为一些子列表，再对每一个子列表进行插入排序，再对每一个子列表执行插入排序

这里有一个含九个元素的列表，如果我们以3为间隔来划分，就会出现三个子列表，每一个可以执行插入排序

python 搜索JIRA python 搜索顺序调整_后端_06

由于每趟都能使得列表更加接近有序，这过程会减少很多原先需要的“无效”比对

希尔排序时间复杂度大致介于 O(n) ~ O(n²)
如果时间间隔保持在 2^{k-1(1、3、5、7、15、31等)，时间复杂度大约为O(n}3/2)

解释：

选择增量 gap=len(arr)/2 ，缩小增量继续以 gap=gap/2 的方式
初始增量为 gap=len(arr)/2=x ，整个数组分成了x组
对这分开的x组分别使用插入排序
缩小增量 gap=gap/2 ，整哥数组分成了 x/2 组
对这分开的 x/2 组分别使用插入排序
直到整个数组只剩1组，只需要进行微调即可完成

python版本

def ShellSort(alist):
    sublistcount = len(alist) // 2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist, startposition, sublistcount)
        print("After increment of size", sublistcount, "The list is", alist)
        sublistcount //= 2


def gapInsertionSort(alist, start, gap):
    for i in range(start+gap, len(alist), gap):
        currentValue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentValue:
            alist[position] = alist[position-gap]
            position -= gap
        alist[position] = currentValue


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
ShellSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.

js版本

function ShellSort(arr) {
    console.time('希尔排序耗时');
    var len = arr.length,
        temp, gap = 1;
    // 动态定义间隔序列
    while (gap < len / 5) {
        gap = gap * 5 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 5)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i; j > 0 && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }

    console.timeEnd('希尔排序耗时');
    return arr
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(ShellSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.

js另一个版本(易理解)

function ShellSort(arr) {
    console.time('希尔排序耗时');
    var len = arr.length,
        temp, gap = len / 2;
    while (gap > 0) {
        for (var i = gap; i < len; i += gap) {
            temp = arr[i];
            var j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }

    console.timeEnd('希尔排序耗时');
    return arr
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(ShellSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

归并排序

时间复杂度：O(n log n)
空间复杂度：O(n)

自顶向下细分，自底向下合并

归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序

基本结束条件：数据表仅有1个数据，自然是排好序的
缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一
调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表

python 搜索JIRA python 搜索顺序调整_python 搜索JIRA_07

归并排序分为两个过程来分析：分裂和归并

分裂的过程，借鉴二分查找的分析结果，是对数复杂度，时间复杂度为O(log n)
归并的过程，相对于分裂的每个部分，其所有数据项都会被比较和放置一次，所以是线性复杂度，其时间复杂度是O(n)
综合考虑，每次分裂的部分窦性进行一次O(n)的数据项归并，总的时间复杂度是O(nlog n)

具体步骤

递归切分当前数组
如果当前数组数量小于等于1，无需排序，直接返回结果 if (end-start<1)return
否则将当前数组分为两个子数组，递归排序这两个子数组 mergeSort(array, start, mid) mergeSort(array, mid+1, end)
在子数组排序结束后，将子数组的结果归并成排好序的数组

python版本

def MergeSort(alist):
    if len(alist) > 1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        MergeSort(lefthalf)
        MergeSort(righthalf)

        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i+1
            # 拉链式交错把左右半部从小到大归并到结果列表中
            else:
                alist[k] = righthalf[j]
                j = j+1
            k = k+1
            # 归并左半部剩余项
        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i+1
            k = k+1
            # 归并右半部剩余项
        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j+1
            k = k+1


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
MergeSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.

python另一个版本

def MergeSort2(alist):
    # 递归结束条件
    if len(alist) <= 1:
        return alist
    # 分解问题，并递归调用
    middle = len(alist)//2
    left = MergeSort2(alist[:middle])  # 左半部分排好序
    right = MergeSort2(alist[middle:])  # 右半部分排好序
    # 合并左右半部分，完成排序
    merged = []
    while left and right:  # 只要左右半部分都还有数据就进行合并
        if left[0] <= right[0]:  # 左半部分首部和右半部分首部进行对比
            merged.append(left.pop(0))  # 哪个小就添加到前面，同时把它删除掉
        else:
            merged.append(right.pop(0))
    # 循环后可能有剩也可能没有
    merged.extend(right if right else left)  # 无论左右只要还有剩的，就归并到列表的后面
    return merged


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
test = MergeSort2(testlist)
print(test)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

js版本

function MergeSort(arr) {
    var len = arr.length;
    if (len <= 1) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return Merge(MergeSort(left), MergeSort(right));
}

function Merge(left, right) {
    var result = [];
    while (left.length && right.length) {
        // 哪个小就添加到前面，同时把它删除掉
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) {
        result.push(left.shift())
    }
    while (right.length) {
        result.push(right.shift())
    }
    return result
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(MergeSort(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.

快速排序

时间复杂度：O(n log n)
空间复杂度：O(log n)

快速排序思路：依据一个“中值”数据项来把数据表分为两半：小于中值的一般和大于中值的一般，然后每部分分别进行快速排序（递归）

基本结束条件：数据表仅有1个数据项，自然是排好序的
缩小规模：依据“中值”，将数据表分为两半，最好情况是相等规模的两半
调用自身：将两半分别调用自身进行排序（排序基本操作在分裂过程中）

python 搜索JIRA python 搜索顺序调整_冒泡排序_08

分裂数据表的目标：找到“中值”的位置

分裂数据表的首端

设置左右标（lefmark/rightmark）
左标向右移动，右标向左移动

左标一直向右移动，碰到比中值大的就停止
右标一直向左移动，碰到比中值小的就停止
然后把左右标所指的数据项交换

继续移动，直到左标移动到右标的右侧，停止移动
这时右标所指位置就是“中值”应处的位置
将中值和这个位置交换
分裂完成，左半部比中值小，右半部比中值大

具体步骤

对于当前数组，取最后一个元素当做基准数（pivot）
将所有比基准数小的元素排到基准数之前，比基准数大的排到基准数之后 quickSort(array, left, partitionIndex-1) quickSort(array, partitionIndex+1, right)
当基准数被放到准确位置之后，根据基准数的位置将数组切分为前后两个子数组
对子数组采用步骤1~4的递归操作，直到子数组的长度小于等于1为止

python版本

def QuickSort(alist):
    QuickSorkHelper(alist, 0, len(alist)-1)


def QuickSorkHelper(alist, first, last):
    # 基本结束条件
    if first < last:
        splitpoint = partition(alist, first, last)
        QuickSorkHelper(alist, first, splitpoint - 1)
        QuickSorkHelper(alist, splitpoint+1, last)


def partition(alist, first, last):
    # 选定中值
    pivotvalue = alist[first]
    # 左右标初始值
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        # 向右移动左标
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
            rightmark -= 1
        # 两标相错就结束移动
        if rightmark < leftmark:
            done = True
        else:
            # 左右标的值交换
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    # 中值就位
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    # 中值点，也是分裂点
    return rightmark


testlist = [1, 2, 32, 8, 17, 19, 42, 13]
QuickSort(testlist)
print(testlist)1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.

c版本（易理解）

#include <stdio.h>
#include <windows.h>

typedef int ElemType;

void Swap(ElemType *p, ElemType *s)
{
    ElemType t;
    t = *p;
    *p = *s;
    *s = t;
}

void Qsort(ElemType A[], int left, int right)
{
    if (left >= right)
    {
        return;
    }
    ElemType pivot = A[right];

    //1.选取一个基准值 pivot
    //2.把基准值元素与 最后一个元素交换
    //3.设置两个索引 i,j:
    //  i从第一个元素开始往右遍历
    //  j从倒数第二个元素开始往左遍历
    int i = left;
    int j = right - 1;

    for (;;)
    {
        //4.两头同时开始遍历
        // i从左->右，找下一个比pivot大(>=)的元素
        while (A[i] < pivot)
            i++;

        // j从右->左，找下一个比pivot小的元素
        while (j >= 0 && A[j] >= pivot)
            j--;

        if (i < j)
        {
            //5.交换
            //交换：把大的元素放在序列的右边
            //     把小的元素放在序列的左边
            Swap(&A[i], &A[j]);
        }
        else
        {
            break;
        }
        //6.i指向的位置就是pivot的位置
        Swap(&A[i], &A[right]);
        //S1: A[left] ... A[i-1]
        Qsort(A, left, i - 1);
        //S2: A[i+1] ... A[right]
        Qsort(A, i + 1, right);
    }
}

//对数组A[n]进行一次快速排序
void QuickSort(ElemType A[], int n)
{
    Qsort(A, 0, n - 1);
}

#define N 10
int main()
{
    int i;
    int a[N];
    //从键盘随机输入一个数组
    for (i = 0; i < N; i++)
    {
        scanf("%d", &a[i]);
    }
    //对数组进行一个快速排序
    QuickSort(a, N);
    //输出
    for (i = 0; i < N; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.

js版本

// 方法1
function QuickSort1(arr, left, right) {
    if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') {
        if (left < right) {
            var x = arr[right],
                i = left - 1,
                temp;
            for (var j = left; j <= right; j++) {
                if (arr[j] <= x) {
                    i++;
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            QuickSort1(arr, left, i - 1);
            QuickSort1(arr, i + 1, right);
        }
        return arr;
    } else {
        return 'array is not an Array or left or right is not a number!';
    }
}
// 方法2
var QuickSort2 = function (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2);
    //把中值删除
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return QuickSort2(left).concat([pivot], QuickSort2(right))
}

var arr = [1, 2, 32, 8, 17, 19, 42, 13];
console.log(QuickSort1(arr, 0, arr.length - 1));
console.log(QuickSort2(arr));1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.

返回上级列表

请

联系我们

，获取更多内容

< 上一篇: Jira使用技巧：项目间移动Issue

下一篇: Jira项目笔记：目录结构与文件管理 >