排序算法Python、Java实现
2021-11-05 本文已影响0人
NLper小白
自己的学习笔记，如有错误，望大家批评指正！！！
1.概念理解
image.png
2.排序算法
image.png
3.十大排序算法的时间复杂度、空间复杂度、稳定性对比
排序算法对比.png
4.排序算详解
4.1 冒泡排序(Bubble Sort)
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
4.1.1 算法描述
image.png
4.1.2 代码实现
- Python代码
"""冒泡排序"""
def bubbleSort(arr):
length = len(arr)
for i in range(length):
for j in range(i, length):
if arr[i] > arr[j]:
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
- Java代码
/**
* 冒泡排序
* */
public static void bubbleSort(int[] arr){
int len = arr.length;
for (int i = 0;i < len;i++){
for (int j = i;j < len;j++){
if (arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
4.2 快速排序(Quick Sort)
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4.2.1 算法描述
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 相比冒泡排序，每次交换是跳跃式的
4.2.2 代码实现
- Python代码
"""快速排序"""
def QuickSort(arr, left, right):
# 递归退出的条件
if left >= right:
return
# 设定起始的基准元素
key = arr[left]
# l为序列左边在开始位置的由左向右移动的游标
l = left
# r为序列右边末尾位置的由右向左移动的游标
r = right
while l < r:
# 如果l与r未重合，r(右边)指向的元素大于等于基准元素，则r向左移动
while arr[r] >= key and l < r:
r -= 1
# 走到此位置时r指向一个比基准元素小的元素,将r指向的元素放到l的位置上,此时r指向的位置空着,接下来移动l找到符合条件的元素放在此处
arr[l] = arr[r]
# 如果l与r未重合，l(右边)指向的元素小于等于基准元素，则l向右移动
while arr[l] <= key and l < r:
l += 1
# 此时l指向一个比基准元素大的元素,将l指向的元素放到r空着的位置上,此时l指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
arr[r] = arr[l]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
# 将基准元素放到该位置,
arr[l] = key
# 对基准元素左边的子序列进行快速排序
QuickSort(arr, left, l-1)
# 对基准元素右边的子序列进行快速排序
QuickSort(arr, l+1, right)
- Java代码
/**
* 快速排序
* 分治法
* */
public static void QuickSort(int[] arr,int left,int right){
// 判断终止条件 递归退出的条件
if (arr == null || arr.length == 0){
return;
}
if(left > right){
return ;
}
// 设定起始的基准元素
int key = arr[left];
// l为序列左边在开始位置的由左向右移动的游标
int l = left;
// r为序列右边末尾位置的由右向左移动的游标
int r = right;
while (l < r){
//如果l与r未重合，r(右边)指向的元素大于等于基准元素，则r向左移动
while (arr[r] >= key && l < r){
r--;
}
// 走到此位置时r指向一个比基准元素小的元素,将r指向的元素放到l的位置上,此时r指向的位置空着,接下来移动l找到符合条件的元素放在此处
arr[l] = arr[r];
// 如果l与r未重合，l(右边)指向的元素小于等于基准元素，则l向右移动
while (arr[l] <= key && l < r){
l++;
}
// 此时l指向一个比基准元素大的元素,将l指向的元素放到r空着的位置上,此时l指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
arr[r] = arr[l];
}
//退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
// 将基准元素放到该位置,
arr[l] = key;
// 对基准元素左边的子序列进行快速排序
QuickSort(arr, left, l-1);
// 对基准元素右边的子序列进行快速排序
QuickSort(arr, l+1, right);
}
4.3 简单插入排序(Insertion-Sort)
插入排序的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
4.3.1 算法描述
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
4.3.2 代码实现
- Python代码
"""插入排序"""
def InsertionSort(arr):
length = len(arr)
for i in range(length):
for j in range(i,0,-1):
if arr[j] < arr[j-1]:
temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
- Java代码
/**
* 插入排序
* */
public static void InsertionSort(int[] arr){
int len = arr.length;
for (int i = 1;i < len;i++){
for(int j = i;j > 0;j--){
if (arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
4.4 希尔排序(Shell Sort)
第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
4.4.1 算法描述
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.4.2 代码实现
- Python代码
"""希尔排序"""
def ShellSort(arr):
length = len(arr)
# 1. 设置步长
step = length // 2
while step > 0:
for i in range(step,length):
temp = arr[i]
j = i
while j >= step and arr[j-step] > temp:
arr[j] = arr[j-step]
j -= step
print(i)
print(temp)
arr[j] = arr[i]
step //= 2
- Java代码
/**
*希尔排序
* 是简单插入排序的改进版,它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
*/
public static void ShellSort(int[] arr){
int len = arr.length;
int step = len / 2;
while (step > 0){
for(int i = step;i < len;i++){
int temp = arr[i];
int j = i;
while (j >= step && arr[j-step] > temp){
arr[j] = arr[j-step];
j -= step;
}
arr[j] = temp;
}
step /= 2;
}
}
4.5 选择排序(Selection-sort)
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
4.5.1 算法描述
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)- 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
4.5.2 代码实现
- Python代码
"""选择排序"""
def SelectionSort(arr):
length = len(arr)
for i in range(length-1):
temp = arr[i]
minIndex = i
for j in range(i+1, length):
if arr[j] < arr[minIndex]:
minIndex = j
arr[i] = arr[minIndex]
arr[minIndex] = temp
- Java代码
/**
* 选择排序
* 先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
* 然后，再从剩余未排序元素中继续寻找最小（大）元素，
* 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
* */
public static void SelectionSort(int[] arr){
int len = arr.length;
for(int i = 0;i < len;i++){
int temp = arr[i];
int minIndex = i;
for (int j = i+1;j < len;j++){
if (arr[j] < arr[minIndex]){
minIndex = j;
}
}
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
4.6堆排序(Heap-Sort)
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
4.6.1 算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
4.6.2 代码实现
- Python代码
"""堆排序"""
# 二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k + 1和 2k+2
def heapsort(array):
# 遍历非叶子节点，建立堆结构数组
length = len(array)
for i in range(length-1, -1, -1):
adjustHeap(array, i, length)
print("arr of heap:", array)
# 堆积树建立完成，开始排序
for j in range(length-1, 0 ,-1):
array[0], array[j] = array[j], array[0]
print(array)
adjustHeap(array, 0, j)
# 维护堆的性质
def adjustHeap(array, i, length):
# 对第i号进行堆调整，获取非叶子节点数据
temp = array[i]
# 非叶子节点的左子节点
k = 2 * i + 1
# 遍历对比k后面的节点，把temp放入合理的位置
while k < length:
# k+1 < length 确保有左右节点才比较
if k + 1 < length and array[k] < array[k+1]:
# 如果左子节点比右子节点小，k就切换到右子节点
k += 1
# 如果子节点有更大的
if array[k] > temp:
# 父节点替换为更大的
array[i] = array[k]
# 记录当前最大点位置
i = k
else:
# 因为堆的特点，后面的更不满足
break
# k 切换到下一个左子节点
k = 2 * k + 1
# 此时i是空位，i上层的都比temp大，temp放到这里
array[i] = temp
- Java代码
/**
* 堆排序
* # 二叉树很容易就存储在数组中。
* 位置 k 的节点的父节点位置为 k/2，
* 而它的两个子节点的位置分别为 2k + 1和 2k+2
* */
public static void heapSort(int[] arr){
//遍历非叶子节点，建立堆结构数组
int len = arr.length;
for (int i = (len-1);i > -1;i--){
adjustHeap(arr, i, len);
}
// 堆积树建立完成，开始排序
for (int j = (len-1);j > 0;j--){
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
adjustHeap(arr,0, j);
}
}
// 维护堆的性质:完全二叉树，子节点的值要小于父节点的值
public static void adjustHeap(int[] arr, int i,int len){
//对第i号进行堆调整，获取非叶子节点数据
int temp = arr[i];
// 非叶子节点的左子节点
int k = 2 * i + 1;
// 遍历对比k后面的节点，把temp放入合理的位置
while (k < len){
// k+1 < length 确保有左右节点才比较
if (k + 1 < len && arr[k] < arr[k+1]){
// 如果左子节点比右子节点小，k就切换到右子节点
k += 1;
}
// 如果子节点有更大的
if (arr[k] > temp){
// 父节点替换为更大的
arr[i] = arr[k];
// 记录当前最大点位置
i = k;
}else {
// 因为堆的特点，后面的更不满足
break;
}
// k 切换到下一个左子节点
k = 2 * k + 1;
}
// 此时i是空位，i上层的都比temp大，temp放到这里
arr[i] = temp;
}
4.7归并排序(Merge-Sort)
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
4.7.1 算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
4.7.2 代码实现
- Python代码
"""归并排序"""
def mergeSort(array):
length = len(array)
if length <= 1:
return array
mid = length // 2
left = array[:mid]
right = array[mid:]
return merge(mergeSort(left),mergeSort(right))
# 合并两个有序的数组
def merge(left, right):
array = []
length_left = len(left)
length_rigth = len(right)
l = r = 0
while length_left > l and length_rigth > r:
if left[l] <= right[r]:
array.append(left[l])
l += 1
else:
array.append(right[r])
r += 1
# 谁还有剩余就把谁全部放进去
if l == length_left:
for i in right[r:]:
array.append(i)
else:
for i in left[l:]:
array.append(i)
return array
- Java代码
/**
* 归并排序
* 采用分治法,将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
*
* @return*/
public static void mergeSort(int[] arr){
int[] temp = new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
}
private static void mergeSort(int[] arr,int left,int right,int []temp){
if (left < right){
int mid = (left+right) / 2;
mergeSort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
mergeSort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
// 合并两个有序的数组
public static void merge(int[] arr,int left,int mid,int right,int []temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i <= mid && j <= right){
if (arr[i] <= arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while (i <= mid){
temp[t++] = arr[i++];
}
while (j <= right){
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
4.8 计数排序(Counting-Sort)
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
4.8.1 算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
4.8.2 代码实现
- Python代码
"""计数排序"""
def counting_sort(array):
# 找出数列中最大值和最小值 创建min-max这么多个0用来统计数列中每个值出现的次数，再从最小值依次排放到最大值
# 找到最大值
max_num = max(array)
# 找到最小值
min_num = min(array)
# 负数数列
neg_list = []
# 非负数数列
pos_list = []
# 对负数和非负数分别处理
for num in array:
if num < 0:
neg_list.append(num)
elif num >= 0:
pos_list.append(num)
length_neg_list = len(neg_list)
length_pos_list = len(pos_list)
# 对负数数列进行处理
if length_neg_list != 0:
# 创建从最最小值到0来累计每个负数出现的次数
neg_count_list = [0 for _ in range(min_num, 0)]
length_neg_count_list = len(neg_count_list)
# 对于负数列中的每个值+1操作
for i in range(length_neg_list):
neg_count_list[neg_list[i]] += 1
#初始化排序索引为0
neg_index = 0
# 对于计数列表中的每一项
for i in range(-length_neg_count_list,0):
# 不为0表明有计数
while neg_count_list[i] > 0:
# 依次排放数值
neg_list[neg_index] = i
# 每次排放后索引加1
neg_index += 1
# 每次排放后对应的计数减1
neg_count_list[i] -= 1
if length_pos_list != 0:
# 创建从0到最大值到来累计每个正数出现的次数
pos_count_list = [0 for _ in range(0, max_num+1)]
length_pos_count_list = len(pos_count_list)
# 对于负数列中的每个值+1操作
for i in range(length_pos_list):
pos_count_list[pos_list[i]] += 1
# 初始化排序索引为0
pos_index = 0
# 对于计数列表中的每一项
for i in range(length_pos_count_list):
# 不为0表明有计数
while pos_count_list[i] > 0:
# 依次排放数值
pos_list[pos_index] = i
# 每次排放后索引加1
pos_index += 1
# 每次排放后对应的计数减1
pos_count_list[i] -= 1
result_list = neg_list + pos_list
return result_list
- Java代码
/**
* 计数排序
* */
public static int[] countingSort(int[] arr){
int arr_len = arr.length;
//1.取数组中的最大值和最小值
int max_num = arr[0], min_num = arr[0];
for (int i = 0;i < arr_len;i++){
if (arr[i] > max_num){
max_num = arr[i];
}
if (arr[i] < min_num){
min_num = arr[i];
}
}
// 2. 确定中间数组的长度
int[] new_arr = new int[max_num - min_num + 1];
//3. 统计原数组中值对应到新数组中值出现的次数
for (int i = 0;i < arr_len;i++){
new_arr[arr[i] - min_num] += 1;
}
//4. 创建返回的有序数组
int[] res = new int[arr_len];
//记录数组下标
int index = 0;
//5. 获取排序后的数组
for (int i = 0; i < new_arr.length; i++){
for (int j = 0;j < new_arr[i];j++){
res[index++] = i + min_num;
}
}
return res;
}
4.9桶排序(Bucket-Sort)
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
4.9.1 算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
4.9.2 代码实现
"""桶排序"""
"""
计数排序的改进版
找出数列中最大值和最小值 创建min-max这么多个桶用来统计数列中每个值出现的次数，再从第一个桶倾倒到最后一个桶
"""
def bucket_sort(array):
length_array = len(array)
# 找到最大值
max_num = max(array)
# 找到最小值
min_num = min(array)
bucket_list = [0 for _ in range(max_num-min_num+1)]
length_bucket_list = len(bucket_list)
# 添加值到对应的桶内，对应桶计数+1
for i in range(length_array):
bucket_list[array[i] - min_num] += 1
# 结果列表
print(bucket_list)
result_list = []
for i in range(length_bucket_list):
print(i)
if bucket_list[i] != 0:
result_list += [i+min_num] * bucket_list[i]
return result_list
4.10 基数排序(Radix-Sort)
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
4.10.1 算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
4.10.2 代码实现
"""基数排序"""
"""
比较位数上的值
比较每一位上的数字大小，当每一位比较完成排序也就完成
"""
def radix_sort(array):
# 找到最大值
max_num = max(array)
# 找到最小值
min_num = min(array)
# 负数数列
neg_list = []
# 非负数数列
pos_list = []
# 对负数和非负数分别处理
for num in array:
if num < 0:
neg_list.append(num)
elif num >= 0:
pos_list.append(num)
length_neg_list = len(neg_list)
length_pos_list = len(pos_list)
# 负数进行排序
if length_neg_list != 0:
neg_num_digit = 0
while neg_num_digit < len(str(min_num)):
# 初始化数值列表
neg_values_lists = [[] for _ in range(10)]
# 对于数列中的每个数
for neg_num in neg_list:
neg_values_lists[int(neg_num/(10**neg_num_digit)) % 10].append(neg_num)
print(neg_values_lists)
neg_list.clear()
for neg_value_list in neg_values_lists:
for neg_num in neg_value_list:
neg_list.append(neg_num)
# 比较下一位
neg_num_digit += 1
# 正数进行排序
if length_pos_list != 0:
pos_num_digit = 0
while pos_num_digit < len(str(max_num)):
# 初始化数值列表
pos_values_lists = [[] for _ in range(10)]
# 对于数列中的每个数
for pos_num in pos_list:
pos_values_lists[int(pos_num / (10 ** pos_num_digit)) % 10].append(pos_num)
pos_list.clear()
for pos_value_list in pos_values_lists:
for pos_num in pos_value_list:
pos_list.append(pos_num)
# 比较下一位
pos_num_digit += 1
result_list = neg_list + pos_list
return result_list
