一.时间复杂度分析
- **时间复杂度**：对排序数据的总的操作次数。反应当n变化时，操作次数呈现什么规律
- **空间复杂度**：算法在计算机内执行时所需要的存储空间的容量，它也是数据规模n的函数。
1.例题:
有一个字符串数组，将数组中的每一个字符串按照字母序排序，之后再将整个字符串数组按照字典序排序，时间复杂度多少？
假设最长字符串长度为s,有n个字符串，则每个字符串按照字母序排序时间复杂度为：O(n*slogs)
整个字符串数组按照字典序排序时间复杂度为:O(s*nlogn),所以总的时间复杂度为:O(n*slogs+s*nlogn)
各种排序算法复杂度:
二．各种排序算法
１．冒泡排序：
**复杂度分析：**
- 时间复杂度：若给定的数组刚好是排好序的数组，采用改进后的冒泡排序算法，只需循环一次就行了，此时是最优时间复杂度：O(n)，若给定的是倒序，此时是最差时间复杂度：O(n^2) ，因此综合平均时间复杂度为：O(n^2)
- 空间复杂度：因为每次只需开辟一个temp的空间，因此空间复杂度是：O(1)，是一个原地排序算法，等于的话不做交换，故是一个稳定的排序算法。
步骤：
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。
代码：
"""冒泡排序:从小到大"""def BubbleSort(array):lengths = len(array)for i in range(lengths-1):for j in range(lengths-1-i):if array[j] > array[j+1]:array[j+1], array[j] = array[j], array[j+1]return arrayif __name__ == '__main__':# array=[5,3,5,8,1,-4,56,87]# print(array)# QuickSort(array,0,len(array)-1)# print(array)array = [5, 3, 5, 8, 1, -4, 56, 87]print("Original array: ", array)array = BubbleSort(array)print("BubbleSort: ", array)
c++实现:
//// Created by fzh on /4/29.//#include <iostream>#include <string>using namespace std;void bubbleSort(int* p, int length){for(int i = 0; i < length - 1; i++){for(int j = 0; j<length - i - 1; j++){if(p[j] > p[j + 1]){//cout<<"==arr[j]:"<<arr[j]<<endl;int temp = p[j];p[j] = p[j + 1];p[j + 1] = temp;}}}}int main() {int arr[10] = {2,2,3,5,19,6,7,8,9,10};int length = sizeof(arr)/sizeof(arr[0]);cout<<"==length:"<<length<<endl;bubbleSort(arr, length);for(int i=0; i<10; i++){cout<< "==arr[i]:" <<arr[i] <<endl;}}
2.插入排序
将未排序元素一个个插入到已排序列表中。对于未排序元素，在已排序序列中从后向前扫描，找到相应位置把它插进去；在从后向前扫描过程中，需要反复把已排序元素逐步向后挪，为新元素提供插入空间。空间复杂度是O(1),也就是一个原地排序算法，稳定的排序算法，平均时间复杂度O(n2)，相比冒泡排序其更受欢迎，主要冒泡排序的数据交换要比插入排序复杂，冒泡排序需要三个赋值操作，而插入排序只需要一个。
"""插入排序：从小到大"""def InsertionnSort(array):lengths = len(array)# 从索引位置1开始for i in range(1, lengths):currentValue = array[i] # 当前索引对应的元素数值preIndex = i - 1 # 前一个索引位置# 循环条件: 前一个索引对应元素值大于当前值，前一个索引值大于等于0while array[preIndex] > currentValue and preIndex >= 0:array[preIndex + 1] = array[preIndex] # 前一个索引对应元素值赋值给当前值preIndex -= 1 # 前一个索引位置-1# preIndex+1，实现元素交换array[preIndex + 1] = currentValuereturn arrayarray = [1, 0, 8, -2, 3, 6, 9]print("Original array={}".format(array))array = InsertionnSort(array)print("InsertionSort={}".format(array))
def insert_sort():a = [9, 8, 3, -3, -7, 1, -5]for i in range(1,len(a)):# value = a[i]for j in range(0,i-1):if a[j]>a[i]:a[j],a[i]=a[i],a[j]print(a)
3.选择排序
说明：首先在未排序序列中找到最小（大）元素，与起始位置元素进行交换，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后在交换。以此类推，直到所有元素均排序完毕。空间复杂度是O(1)，是原地排序算法，平均时间复杂度是O(n2)，是不稳定的排序算法，因为每次都要找未排序的最小值交换，
比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序，2要跟第一个5发生交换，那么这两个5的顺序就发生了变化，
def SelectionSort(arr):for i in range(len(arr)-1):minIndex=ifor j in range(i+1,len(arr)):if arr[j]<arr[minIndex]:minIndex=jif i!=minIndex:arr[i],arr[minIndex]=arr[minIndex],arr[i]return arrarr=[-1,-3,-6,3,4,0,2]print(arr)arr=SelectionSort(arr)print(arr)
4.归并排序
归并排序和快速排序，时间复杂度为O(nlogn)，更适合大规模的数据排序，采用了分治的思想，由于借用temp数组，故空间复杂度为O(n)，，是一个稳定的排序算法。
写法1:
def Merge(q, r):left, right = 0, 0result = []while left < len(q) and right < len(r):# 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置if q[left] < r[right]:result.append(q[left])left += 1else:result.append(r[right])right += 1result += q[left:] # 若最后left列表剩余，则将其剩余部分加入到result后面result += r[right:] # 若最后right列表剩余，则将其剩余部分加入到result后面return resultdef Merge_Sort(L):if len(L) <= 1:return Lmid = len(L) // 2 # 这里的//是python3中除以后取整的用法，大家不要以为我打错了～q = Merge_Sort(L[:mid])r = Merge_Sort(L[mid:])return Merge(q, r)a=[1,2,9,0,8,2,3]b=Merge_Sort(a)print(b)
写法2:
class Solution:def mergeSort(self, nums, start, end):if start >= end:returnmid = start + (end - start) // 2self.mergeSort(nums, start, mid)self.mergeSort(nums, mid + 1, end)self.merge(nums, start, mid, end)def merge(self, nums, start, mid, end):i, j, temp = start, mid + 1, []while i <= mid and j <= end:if nums[i] <= nums[j]:temp.append(nums[i])i += 1else:t += mid - i + 1temp.append(nums[j])j += 1while i <= mid:temp.append(nums[i])i += 1while j <= end:temp.append(nums[j])j += 1for i in range(len(temp)):nums[start + i] = temp[i]print('==nums:', nums)def reversePairs(self, nums):t = 0self.mergeSort(nums, 0, len(nums) - 1)print('==after nums:', nums)return tnums = [7,5,6,4]sol = Solution()sol.reversePairs(nums)print(t)
k路归并排序:
给出K个有序的数组现在将其归并成一个有序数组怎么做最快。
def Merge(q, r):left, right = 0, 0result = []while left < len(q) and right < len(r):# 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置if q[left] < r[right]:result.append(q[left])left += 1else:result.append(r[right])right += 1result += q[left:] # 若最后left列表剩余，则将其剩余部分加入到result后面result += r[right:] # 若最后right列表剩余，则将其剩余部分加入到result后面return resultdef Merge_Sort(L):if len(L) <= 1:return L[0]mid = len(L) // 2q = Merge_Sort(L[:mid])r = Merge_Sort(L[mid:])print('==q==:', q)print('==r==:', r)return Merge(q, r)# a = [1, 2, 9, 0, 8, 2, 3]a = [[1, 2],[0, 3],[-4, 8]]b = Merge_Sort(a)print('==b:', b)
５．快速排序
思想：通过一趟排序将待排列表分成独立的两部分，其中一部分的所有元素均比另一部分的元素小，则分别对这两部分继续重复进行此操作，以达到整个序列有序。
步骤：
使用分治法把一个串分为两个子串，具体算法描述如下：
1，从数列中挑出一个元素，称为'基准'(privot)，本文将第一个选为基准；
2，比基准数小的所有元素放在基准前面，比基准数大的所有元素放在基准后面，这样完成了分区操作;
3，递归地把小于基准值元素的子数列和大于基准值元素的子数列按上述操作进行排序，递归结束条件序列的大小为0或1。
根据分治，递归的处理思想，利用递归排序下标从p到q-1之间的数据，和下标从q+1到r之间的数据，直至区间缩小为1，说明所有的数据都有序了，跟归并排序不同的是，要做成原地排序算法，不借用temp，空间复杂度为O（1），时间复杂度为O（nlogn）。由于涉及到选择基准，倘若基准是两个相同的数，经过分区处理后，顺序可能发生变化，故是不稳定的算法。
流程：
代码：
def QuickSort(array,start,end):length=len(array)i=startj=endif i>=j:returnprivot=array[i]while i<j:#从右往左while i<j and privot<=array[j]:j-=1array[i]=array[j]# print(array)# 从左往右while i < j and privot >= array[i]:i+= 1array[j] = array[i]# print(array)array[i]=privot# print(array)#QuickSort(array,start,i-1)QuickSort(array, i+1, end)if __name__ == '__main__':array=[5,3,5,8,1,-4,56,87]print(array)QuickSort(array,0,len(array)-1)print(array)
更快的方式：
#选择中间的数作为基准def quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]print('left=',left)middle = [x for x in arr if x == pivot]print('middle=', middle)right = [x for x in arr if x > pivot]print('right=', right)return quicksort(left) + middle + quicksort(right)if __name__ == '__main__':print(quicksort([9,8,7,6,5,43,2]))
６．桶排序
桶排序，将要排序的数据分到几个有序的桶里，每个桶里的数据单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。桶排序的时间复杂度为什么是 O(n)呢？排序数据有n个，均匀划分到m个桶内，每个桶就有k=n/m个元素，每个桶使用快速排序，时间复杂度为O(k*logk)。m个桶排序时复杂度就是O(m*k*logk),故整个桶排序时间复杂度就是O(n*(log(n/m))),m足够大时，log(n/m)是一个很小的值，故时间复杂度接近O(n)。极端情况下，分到一个桶里，就变为O(n*logn),其适合外部排序，也就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。其是一个稳定的排序算法。
７．计数排序
计数排序可以看成是桶排序的一种特设请情况，考生的满分是 900 分，最小是 0 分，这个数据的范围很小,可以分成901个桶，将50万考生划分到901个桶，桶内的数据是相同分数的考生，只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，即实现排序，也就是计数排序，其只适合于数据范围不大的场景，如果数据范围k比排序数据n大很多，就不是和计数排序了，而且只适合给非负整数排序，若有负数，需要转换成正数，归一化。其是一个稳定的排序算法，时间复杂度O(n)，
８．基数排序
基数排序，假设有10万个手机号码，希望将这10万个手机号码按下到大排序，时间复杂度O(n)，基数排序对要排序的数据是有要求的，需要可以分割出独立的‘位’来比较，而且具有递进的关系。其是一个稳定的排序算法。
下面用字母来代替。
总结：Glibc的qsort（）函数会优先使用归并排序，对于1k，2k左右的数据，完全可以用空间換时间，因为其空间复杂度是O(n)，时间复杂度是O(nlogn)。
对于小数量数据的排序，O(n2)的排序算法并不一定比O(nlogn)排序算法执行时间长，对于小数据的排序，选择简单，
不需要递归的插入排序算法，递归过深容易导致堆栈溢出。
数据量较大的情况就用快速排序，分区点的选择可以用三数取中法和随机法
1,三数取中法，从区间的首，尾，中间分别取出一个数，然后比对大小，取这三个数的中间值作为分区点，如果排序的数组很大，可能就要用多个数来取中间值。
2,随机法，每次从要排序的区间，随机选择一个元素作为分区点，从概率的角度讲不会出现每个分区点都会选的很差的情况。
