算法和数据操作—查找和排序_下面查找算法中什么的空间复杂度为o 顺序查找

目录

查找

一、查找分类

二、顺序表查找

1. 顺序查找

2. 二分查找

三、树表查找

1. 二叉排序树查找

四、散列表（哈希表）查找 

1. 哈希表查找

排序

一、排序的基本概念

二、排序分类

1. 冒泡排序

2. 选择排序

3. 插入排序

4. 堆排序

5. 归并排序

6. 快速排序

三、排序总结

1. 排序算法分类

2. 七种排序算法性能对比

---

查找

一、查找分类

二、顺序表查找

1. 顺序查找

顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。

基本思路

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

优缺点

• 缺点：当n很大时，平均查找长度较大，效率低；
• 优点：对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

代码： 

class Solution():
    def sequentialSearch(self, arr, item):
        for index, data in enumerate(arr):
            if data == item:
                return index
 
if __name__ == "__main__":
    arr = [1,3,5,7,9]
    s = Solution()
    item = 1
    print(s.sequentialSearch(arr, item))

2. 二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

• 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
• 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表
• 否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

非递归实现二分查找 代码如下

"""
最优时间复杂度：O(1)
最坏时间复杂度：O(logn)
"""
def binary_search(list,target):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == target:
            return mid
        if guess < target:
            low = mid + 1
        else:
            high = mid -1
    return None
 
if __name__ == "__main__":
    s = [1,3,5,7,9]
    item = 1
    print(binary_search(s,item))

三、树表查找

1. 二叉排序树查找

构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。

二叉排序树的操作：

• 查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。
• 插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。
• 删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

代码：

class BSTNode:
    """
    定义一个二叉树节点类。
    以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
    """
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
class BinarySortTree:
    """
    基于BSTNode类的二叉排序树。维护一个根节点的指针。
    """
    def __init__(self):
        self._root = None
 
    def is_empty(self):
        return self._root is None
 
    def search(self, key):
        """
        关键码检索
        :param key: 关键码
        :return: 查询节点值或None
        """
        bt = self._root
        while bt:
            entry = bt.data
            if key < entry:
                bt = bt.left
            elif key > entry:
                bt = bt.right
            else:
                return entry
        return None
 
    def insert(self, key):
        """
        插入操作
        :param key:关键码 
        :return: 布尔值
        """
        bt = self._root
        if not bt:
            self._root = BSTNode(key)
            return
        while True:
            entry = bt.data
            if key < entry:
                if bt.left is None:
                    bt.left = BSTNode(key)
                    return
                bt = bt.left
            elif key > entry:
                if bt.right is None:
                    bt.right = BSTNode(key)
                    return
                bt = bt.right
            else:
                bt.data = key
                return
 
    def delete(self, key):
        """
        二叉排序树最复杂的方法
        :param key: 关键码
        :return: 布尔值
        """
        p, q = None, self._root     # 维持p为q的父节点，用于后面的链接操作
        if not q:
            print("空树！")
            return
        while q and q.data != key:
            p = q
            if key < q.data:
                q = q.left
            else:
                q = q.right
            if not q:               # 当树中没有关键码key时，结束退出。
                return
        # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
        if not q.left:
            if p is None:
                self._root = q.right
            elif q is p.left:
                p.left = q.right
            else:
                p.right = q.right
            return
        # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
        # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
        r = q.left
        while r.right:
            r = r.right
        r.right = q.right
        if p is None:
            self._root = q.left
        elif p.left is q:
            p.left = q.left
        else:
            p.right = q.left
 
    def __iter__(self):
        """
        实现二叉树的中序遍历算法,
        展示我们创建的二叉排序树.
        直接使用python内置的列表作为一个栈。
        :return: data
        """
        stack = []
        node = self._root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.data
            node = node.right
 
 
if __name__ == '__main__':
    lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
 
    bs_tree = BinarySortTree()
    for i in range(len(lis)):
        bs_tree.insert(lis[i])
    # bs_tree.insert(100)
    # bs_tree.delete(58)
    for i in bs_tree:
        print(i, end=" ")
    print("\n", bs_tree.search(58))

二叉排序树总结：

• 二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。
• 在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。
• 给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。
• 当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。

四、散列表（哈希表）查找 

1. 哈希表查找

算法简介

   哈希表就是一种以键-值(key-indexed) 存储数据的结构，只要输入待查找的键即key，即可查找到其对应的值。

算法思想

    哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

算法流程

　　1）用给定的哈希函数构造哈希表；
　　2）根据选择的冲突处理方法解决地址冲突；
　　　　 常见的解决冲突的方法：拉链法和线性探测法。
　　3）在哈希表的基础上执行哈希查找。

复杂度分析

　　单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

算法实现

class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长
 
    def hash(self, key):
        return key % self.count  # 散列函数采用除留余数法
 
    def insert_hash(self, key):
        """插入关键字到哈希表内"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 当前位置已经有数据了，发生冲突。
            address = (address+1) % self.count  # 线性探测下一地址是否可用
        self.elem[address] = key  # 没有冲突则直接保存。
 
    def search_hash(self, key):
        """查找关键字，返回布尔值"""
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True
 
 
if __name__ == '__main__':
    list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    hash_table = HashTable(12)
    for i in list_a:
        hash_table.insert_hash(i)
 
    for i in hash_table.elem:
        if i:
            print((i, hash_table.elem.index(i)), end=" ")
    print("\n")
 
    print(hash_table.search_hash(15))
    print(hash_table.search_hash(33))

排序

一、排序的基本概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

排序的稳定性：
经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。

二、排序分类

按照算法复杂度可分为两类：

• 简单算法：包括冒泡排序、简单选择排序和直接插入排序
• 改进算法：包括希尔排序、堆排序、归并排序和快速排序

1. 冒泡排序

冒泡排序（bubbleSort）工作原理：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

伪码：

bubbleSort(arry)
    for i from 0 to len(arr)-1
        for j from 0 to len(arr)-i-1
            if arr[j] > arr[j+1] then Exchange arr[j],arr[j+1]
        end for
    end for

代码：

#include <iostream>
#include <algorithm>
 
using namespace std;
 
void bubbleSort(int arr[], int len) {
	for (int i = 0; i < len - 1; ++i)
	{
		for (int j = 0; j < len - i - 1; ++j)
		{
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
		}
	}
}
int main() {
	int arr[6] = { 6,7,4,3,11,5 };
 
	bubbleSort(arr, 6);
	for (int i : arr)
		cout << i << " ";
 
	system("pause");
	return 0;
}

冒泡排序优化：

设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。时间复杂度O(n^2)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
void bubbleSort(int arr[], int len) {
	for (int i = 0; i < len - 1; ++i)
	{
		bool exchangeFlag = false;
		for (int j = 0; j < len - i - 1; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(arr[j], arr[j + 1]);
				exchangeFlag = true;
			}
		}
		if (exchangeFlag == false)
			break;
	}
}
int main() {
	int arr[6] = { 6,7,4,3,1,5 };
 
	bubbleSort(arr, 6);
	for (int i : arr)
		cout << i << " ";
 
	system("pause");
	return 0;
}

2. 选择排序

简单选择排序（simple selection sort）:时间复杂度O(n^2)
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n)个记录进行交换。

通俗的说就是，对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于，每一轮中比较了很多次，但只交换一次。因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。

伪码：

selectSort(arr)
for i from 1 to len(arr)-1
       k = i       //设立标志位
       for j from i+1 to len(arr)     //查找第i小的元素
            if A[j]<A[k]    then k = j
       end for
       if k ≠ i    then Exchange A[i],A[k]
end for

python代码：

def selectSort(lst):
    for i in range(len(lst)-1):
        k = i
        for j in range(i+1,len(lst)):
            if lst[j] < lst[k]:
                k = j
        lst[i],lst[k] = lst[k],lst[i]
    return lst

3. 插入排序

插入排序(insertionSort)的工作原理：

对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度O(n^2)

伪码：

​

python代码：

def insertSort(Lst):
    for i in range(1, len(Lst)):
        key = Lst[i]
        j = i
        while j > 0 and Lst[j-1] > key: #找合适的插入位置
            Lst[j], Lst[j-1] = Lst[j-1], Lst[j]         
            j -= 1
    return Lst

该算法需要一个记录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为O(n)。然而，这基本是幻想 。

4. 堆排序

堆

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

​

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

​

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

• 父节点i的左子节点在位置(2*i+1);
• 父节点i的右子节点在位置(2*i+2);
• 子节点i的父节点在位置(i-1)//2;

堆排序基本思想及步骤

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次大值。如此反复执行，便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.假设给定无序序列结构如下

​

2.从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点）或者arr.length-2)//2，从左至右，从下至上进行调整。

​

3.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

​

4.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

 ​

此时，我们就将一个无需序列构造成了一个大顶堆

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

1.将堆顶元素9和末尾元素4进行交换

​

2.重新调整结构，使其继续满足堆定义

​

3.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

​

4.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

​

再简单总结下堆排序的基本思路（这里用最大堆的情况）：

• 最大堆调整(MAX_Heapify):将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较 i 的根节点和与其所对应i的孩子节点的值。当 i 根节点的值比左孩子节点的值要小的时候，就把 i 根节点和左孩子节点所对应的值交换，当 i 根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。 
• 建立最大堆(Build_Max_Heap):将堆所有数据重新排序。建堆的过程其实就是不断做最大堆调整的过程，从 len/2 出发开始调整，一直到第一个节点。 
• 堆排序(HeapSort):移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。首先先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面 len-1 个节点继续做堆调整的过程。直到将所有的节点取出，对于 n 个数我们只需要做 n-1 次操作。

代码：

#include<iostream>
#include<vector>
using namespace std;
 
/* 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)*/
void adjust(vector<int> &arr, int len, int index)
{
	int left = 2 * index + 1; // index的左子节点
	int right = 2 * index + 2;// index的右子节点
 
	int maxIdx = index;
	if (left < len && arr[left] > arr[maxIdx])     maxIdx = left;
	if (right < len && arr[right] > arr[maxIdx])     maxIdx = right;
 
	if (maxIdx != index)
	{
		swap(arr[maxIdx], arr[index]);
		adjust(arr, len, maxIdx);
	}
}
 
// 堆排序
void heapSort(vector<int> &arr, int size)
{
	// 构建大根堆（从最后一个非叶子节点向上）
	for (int i = size / 2 - 1; i >= 0; --i)
	{
		adjust(arr, size, i);
	}
 
	// 调整大根堆
	for (int i = size - 1; i >= 1; --i)
	{
		swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
		adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
	}
}
 
int main()
{
	vector<int> arr = { 8, 1, 14, 3, 21, 5, 7, 10 };
	heapSort(arr, arr.size());
	for (int i = 0;i < arr.size();++i)
		cout << arr[i] << " ";
	cout << endl;
	system("pause");
	return 0;
}

堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。其初始构建堆时间复杂度为O(n)。正式排序时，重建堆的时间复杂度为O(nlogn)。所以堆排序的总体时间复杂度为O(nlogn)。

堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。

5. 归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

伪码：

python代码： 

​def Merge(a,p,q,r):
    leftArray=[]
    rightArray=[]
    n1=q-p+1+1
    n2=r-q+1
    for num in range(1,n1):
        index=num+p-1
        leftArray.append(a[index])
    leftArray.append(float("inf"))
    for num in range(1,n2):
        index=num+q 
        rightArray.append(a[index])
    rightArray.append(float("inf"))
    i=0
    j=0
 
    for k in range(p,r+1):
        if(leftArray[i]<=rightArray[j]):
            a[k]=leftArray[i]
            i=i+1
        else:
            a[k]=rightArray[j]
            j=j+1
 
def Merge_Sort(a,p,r):
	if(p<r):
		q=int((p+r)/2) 
		Merge_Sort(a,p,q)  #排序数组的半部分
		Merge_Sort(a,q+1,r) #排序数组的后半部分
		Merge(a,p,q,r) #将两个排序好的数组 合并
	return a	

• 归并排序对原始序列元素分布情况不敏感，其时间复杂度为O(nlogn)。

• 归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。

• 归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。

总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。

6. 快速排序

快速排序采用分治算法，基本思想：首先任意选取一个数据作为关键数据（pivot），然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

步骤如下：

1.选取一个数字作为基准，可选取末位数字

2.将数列第一位开始，依次与此数字比较，如果小于此数，将小数交换到左边，最后达到小于基准数的在左边，大于基准数的在右边，分为两个数组

3.分别对两个数组重复上述步骤

其中一次排序步骤如下：

伪码实现：

Partition(A,p,r)
    pivot=A[r]
    i=p-1
    for j from p to r-1
        if A[j]<=pivot
            then i=i+1
                exchange A[i],A[j]
    exchange A[i+1],A[r]
    return i+1
 
QuickSort(A,p,r)
    if p<r
        then q = Partition(A,p,r)
            QucikSort(A,p,q-1)
            QucikSort(A,q+1,r)

递归版本：

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int partition(int arr[], int left, int right) {
	int pivot = arr[left];
	swap(arr[left], arr[right]);//将pivot换到最后
	int index = left - 1;
	//将小于pivot的元素放到左边，大的放到右边
	for (int i = left; i < right; ++i)
	{
		if (arr[i] < pivot)
		{
			++index;
			swap(arr[i], arr[index]);
		}		
	}
	++index;
	swap(arr[index], arr[right]);
	return index;
}
 
void quickSort(int arr[], int left, int right) {
	if (left < right)
	{
		int pos = partition(arr, left, right);
		if(pos > left)
			quickSort(arr, left, pos - 1);
		if(pos < right)
			quickSort(arr, pos + 1, right);
	}
	return;
}
 
int main() {
	int arr[6] = { 6,7,4,3,1,5 };
 
	quickSort(arr, 0, 5);
	for (int i : arr)
		cout << i << " ";
 
	system("pause");
	return 0;
}

随机化版本 ：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
 
using namespace std;
 
int randominrange(int start, int end) {
	srand((unsigned)time(NULL));
	return (rand() % (end - start + 1) + start);
}
 
int partition(int arr[], int left, int right) {
	int pivotindex = randominrange(left, right);
	swap(arr[pivotindex], arr[right]);//将pivot换到最后
	int index = left - 1;
	//将小于pivot的元素放到左边，大的放到右边
	for (int i = left; i < right; ++i)
	{
		if (arr[i] <arr[right])
		{
			++index;
			swap(arr[i], arr[index]);
		}
	}
	++index;
	swap(arr[index], arr[right]);
	return index;
}
 
void quick_sort(int arr[], int left, int right) {
	if (left == right)
		return;
	int pos = partition(arr, left, right);
	if (pos > left)
		quick_sort(arr, left, pos - 1);
	if (pos < right)
		quick_sort(arr, pos + 1, right);
}
 
int main() {
	int arr[6] = { 1,17,14,3,5,12 };
 
	quick_sort(arr, 0, 5);
	for (int i : arr)
		cout << i << " ";
 
	system("pause");
	return 0;
}

时间复杂度

        快速排序涉及到递归调用，所以该算法的时间复杂度还需要从递归算法的复杂度开始说起；

       递归算法的时间复杂度公式：T[n] = aT[n/b] + f(n)  ；对于递归算法的时间复杂度这里就不展开来说了；

• 最优情况下时间复杂度

        快速排序最优的情况就是每一次取到的元素都刚好平分整个数组，此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)。T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；

        下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：

                                         T[n] =  2T[n/2] + n                                                                ----------------第一次递归

                 令：n = n/2        =  2 { 2 T[n/4] + (n/2) }  + n                                               ----------------第二次递归

                                            =  2^2 T[ n/ (2^2) ] + 2n

                令：n = n/(2^2)   =  2^2  {  2 T[n/ (2^3) ]  + n/(2^2)}  +  2n                         ----------------第三次递归  

                                            =  2^3 T[  n/ (2^3) ]  + 3n

                ......................................................................................                        

                令：n = n/(  2^(m-1) )    =  2^m T[1]  + mn                                                  ----------------第m次递归(m次后结束)

               当最后平分的不能再平分时，也就是说把公式一直往下迭代，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。

               得到：T[n/ (2^m) ]  =  T[1]    ===>>   n = 2^m   ====>> m = logn；

               T[n] = 2^m T[1] + mn ；其中m = logn;

               T[n] = 2^(logn) T[1] + nlogn  =  n T[1] + nlogn  =  n + nlogn  ；其中n为元素个数

               又因为当n >=  2时：nlogn  >=  n  (也就是logn > 1)，所以取后面的 nlogn；

               综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )

• 最差情况下时间复杂度

        最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)，这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

       综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )

      为了避免最差情况，可采用“三数取中法”，每次随机从数组中选取三个数，选择中间值作为Pivot。

• 平均时间复杂度

       快速排序的平均时间复杂度也是：O(nlogn)

       证明：https://www.cnblogs.com/LzyRapx/p/9565827.html

• 空间复杂度

        其实这个空间复杂度不太好计算，因为有的人使用的是非就地排序，那样就不好计算了（因为有的人用到了辅助数组，所以这就要计算到你的元素个数了）；我就分析下就地快速排序的空间复杂度吧；

        首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；

     最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况

     最差的情况下空间复杂度为：O( n )；退化为冒泡排序的情况

三、排序总结

1. 排序算法分类

2. 六种排序算法性能对比

稳定性的定义

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

判断方法

对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a[j].key>=a[j+1].key，则两个相等的记录就会交换位置。