从前向后遍历待排序列，依次比较相邻两个元素，发现逆序则交换两个元素的位置，遍历一遍为一趟，重复遍历，直到某一趟下来未发生交换，则序列为有序序列，含有n个元素的序列最多遍历n-1趟。
2.动态演示 3.python代码def bubblesort(nums):
# 使用for循环控制遍历次数，最多len(nums)-1次
for i in range(len(nums) - 1):
# 定义boolean型变量swap记录是否发生交换，刚开始未发生交换，因此初始值为false
swap = False
# 使用for循环控制待排序列的长度，每多一趟待排序列长度减1
for j in range(len(nums) - 1 - i):
# 如果逆序，则交换两个元素的位置
if nums[j] > nums[j+1]:
tmp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = tmp
# 发生交换，swap应变为true
swap = True
# 如果这趟未发生交换，则序列为有序序列，冒泡排序终止
if not swap:
break
return nums
# 测试
list1 = [1, 2, 3, 7, 6, -1, 0, 8, 5, 4]
list2 = bubblesort(list1)
print(list2)
运行结果 ：
4.Java代码import java.util.Arrays;
public class BubbleSort {
public static int[] bubbleSort(int[] nums) {
//定义整型变量len获取待排序列的长度
int len = nums.length;
//定义for循环控制遍历次数，最多len-1次
for(int i=0;i nums[j+1]) {
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
//发生交换，swap应变为true
swap = true;
}
}
//如果这趟未发生交换，则序列为有序序列，冒泡排序终止
if(swap == false) {
break;
}
}
return nums;
}
//测试
public static void main(String[] args) {
int[] list1 = new int[]{1, 2, 3, 7, 6, -1, 0, 8, 5, 4};
int[] list2 = BubbleSort.bubbleSort(list1);
System.out.println(Arrays.toString(list2));
}
}
运行结果：
二、快速排序 1.基本思想从待排序列中任意选择一个数作为标准（一般选取第一个数），将待排序列分为左右两个子序列，左子序列中的数都小于标准，右子序列中的数都大于等于标准。然后分别在左右子序列中执行以上操作，直到每一个序列只有一个元素时停止，此时的序列为有序序列。
2.动态演示
3.python代码
# nums：待排序列，head：本次排序中序列的头，tail：本次排序中序列的尾
def quicksort(nums, head, tail):
# 如果待排序列中只有一个元素，则序列为有序序列，返回即可
if head >= tail:
return nums
# 选择待排序列中的第一个元素作为标准
standard = nums[head]
# 用start标记左边扫描的起始位置
start = head
# 用end标记右边扫描的起始位置
end = tail
# 用while循环控制一次划分
while start < end:
# 从右到左寻找待排序列中小于标准的元素
while start < end and standard <= nums[end]:
end -= 1
# 找到后将其放置在start标记的位置
nums[start] = nums[end]
# 从左到右寻找待排序列中大于标准的元素
while start < end and standard >= nums[start]:
start += 1
# 找到后将其放置在end标记的位置
nums[end] = nums[start]
# 当start=end时，这个位置就是标准所在的位置
nums[end] = standard
# 对左子序列进行划分
quicksort(nums, head, end - 1)
# 对左子序列进行划分
quicksort(nums, end + 1, tail)
return nums
# 测试
list1 = [1, 2, 3, 7, 6, -1, 0, 8, 5, 4]
list2 = quicksort(list1, 0, len(list1)-1)
print(list2)
运行结果：
4.Java代码import java.util.Arrays;
public class QuickSort {
// nums：待排序列，head：本次排序中序列的头，tail：本次排序中序列的尾
public static int[] quickSort(int[] nums,int head,int tail) {
if(head >= tail) {
return nums;
}
// 选择待排序列中的第一个元素作为标准
int standard = nums[head];
// 用start标记左边扫描的起始位置
int start = head;
// 用end标记右边扫描的起始位置
int end = tail;
// 用while循环控制一次划分
while(start < end) {
// 从右到左寻找待排序列中小于标准的元素
while(start < end && standard <= nums[end]) {
end -= 1;
}
// 找到后将其放置在start标记的位置
nums[start] = nums[end];
// 从左到右寻找待排序列中大于标准的元素
while(start < end && standard >= nums[start]) {
start += 1;
}
// 找到后将其放置在end标记的位置
nums[end] = nums[start];
}
// 当start=end时，这个位置就是标准所在的位置
nums[end] = standard;
// 对左子序列进行划分
quickSort(nums, head, end - 1);
// 对右子序列进行划分
quickSort(nums, end + 1, tail);
return nums;
}
//测试
public static void main(String[] args) {
int[] list1 = new int[]{1, 2, 3, 7, 6, -1, 0, 8, 5, 4};
int[] list2 = QuickSort.quickSort(list1,0,list1.length-1);
System.out.println(Arrays.toString(list2));
}
}
运行结果：
三、选择排序 1.基本思想选择待排序列中最小（大）的元素，将其与序列中第一个元素交换位置；然后将第二个元素开始到最后一个元素结尾的序列作为待排序列，找出其中最大的元素，与第二个元素交换位置；然后从第三个元素开始重复以上操作，当待排序列只剩最后一个元素序列有序。
2.动态演示 3.Python代码def selectsort(nums):
# 外层循环控制交换次数
for i in range(len(nums)-1):
# 假设最前面等待交换的元素为目前最小元素
min_index = i
# 寻找最小元素的索引
for j in range(i+1, len(nums)):
# 与目前最小元素比较，如果该元素更小
if nums[j] < nums[min_index]:
# 则将目前最小元素的索引更新为该元素的索引
min_index = j
# 与最小元素交换位置
tmp = nums[i]
nums[i] = nums[min_index]
nums[min_index] = tmp
return nums
# 测试
list1 = [1, 2, 3, 7, 6, -1, 0, 8, 5, 4]
list2 = selectsort(list1)
print(list2)
运行结果：
4.Java代码import java.util.Arrays;
public class SelectSort {
public static int[] selectSort(int[] nums) {
// 外层循环控制交换次数
for(int i=0;i
运行结果：
四、插入排序
1.基本思想
将未排序元素逐一拿到已排序序列中与已排序元素进行比较，找到合适的位置将其插入。
2.动态演示
3.Python代码
def InsertSort(nums):
# 假定初始时第一个元素为已排序列表，其余元素为未排序列表
# 遍历未排序列表
for i in range(1, len(nums)):
# 标记取出元素的位置（该位置留空）
index = i
# 取出未排序列表中的第一个元素
item = nums[index]
# 从后往前遍历已排序列表元素
for j in range(i-1, -1, -1):
# 若已排序列表中的元素大于取出元素
if nums[j] > item:
# 将已排序列表中的这个元素向后移一位
nums[index] = nums[j]
# 留空位置前移一位
index -= 1
# 当j=0，意味着已排序列表中的元素全部大于取出元素，此时已排序列表最前端留空
if j == 0:
# 将取出元素插入留空位置
nums[j] = item
# 若已排序列表中的元素小于等于取出元素
else:
# 将取出元素插入留空位置
nums[index] = item
# 终止此次循环
break
return nums
# 测试
list1 = [1, 2, 3, 7, 6, -1, 0, 8, 5, 4]
list2 = InsertSort(list1)
print(list2)
运行结果：
4.Java代码
import java.util.Arrays;
public class InsertSort {
public static int[] insertSort(int[] nums) {
int len = nums.length;
// 假定初始时第一个元素为已排序列表，其余元素为未排序列表
// 遍历未排序列表
for (int i=1;i-1;j--) {
// 若已排序列表中的元素大于取出元素
if (nums[j] > item) {
// 将已排序列表中的这个元素向后移一位
nums[index] = nums[j];
// 留空位置前移一位
index -= 1;
// 当j=0，意味着已排序列表中的元素全部大于取出元素，此时已排序列表最前端留空
if (j == 0) {
// 将取出元素插入留空位置
nums[j] = item;
}
}
// 若已排序列表中的元素小于等于取出元素
else {
// 将取出元素插入留空位置
nums[index] = item;
// 终止此次循环
break;
}
}
}
return nums;
}
//测试
public static void main(String[] args) {
int[] list1 = new int[]{1, 2, 3, 7, 6, -1, 0, 8, 5, 4};
int[] list2 = InsertSort.insertSort(list1);
System.out.println(Arrays.toString(list2));
}
}
运行结果：
五、堆排序
1.基本思想
- 完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
- 堆：可以看做一棵树的数组对象，它总是满足以下两个特性：
（1）堆中某个结点的值总是不大于（大根堆）或不小于（小根堆）其父结点的值；
（2）堆总是一棵完全二叉树。 - 堆排序：已知堆中根节点要么最大（大根堆），要么最小（小根堆）。
（1）将待排序列建堆；
（2）将根节点和最后一个叶子节点交换，然后将最后一个元素从待排序列中剔除：
（3）重复以上两步，直到待排序列只剩一个元素。
2.动态演示
3.Python代码
# 建大根堆
def BuildHeap(nums):
l = len(nums)
# 根据数组长度计算出最后一个非叶节点的索引
last_parent_index = (l // 2) - 1
# 从最后一个非叶节点开始遍历所有非叶节点
for i in range(last_parent_index, -1, -1):
# 计算其左孩子的索引
left_child_index = 2 * i + 1
# 计算其右孩子的索引
right_child_index = 2 * (i + 1)
# 较大的孩子节点的索引（默认左孩子较大）
bigger_child_index = left_child_index
# 如果右孩子存在且大于左孩子，将较大孩子索引改为右孩子索引
if right_child_index <= l - 1 and nums[right_child_index] > nums[left_child_index]:
bigger_child_index = right_child_index
# 将其与较大孩子比较，孩子更大则与父节点交换位置
if nums[bigger_child_index] > nums[i]:
tmp = nums[bigger_child_index]
nums[bigger_child_index] = nums[i]
nums[i] = tmp
# 堆顶和堆底元素交换
def SwapNode(nums):
tmp = nums[0]
nums[0] = nums[-1]
nums[-1] = tmp
list1 = [1, 2, 3, 7, 6, -1, 0, 8, 5, 4]
# 结果集
result = []
for i in range(len(list1)):
# 建堆
BuildHeap(list1)
# 交换堆顶和堆底元素
SwapNode(list1)
# 将堆底元素从待排序列删除并加入结果集
result.append(list1.pop(-1))
print(result)
运行结果：
4.Java代码
注：由于对Java中的List操作不熟，所以Java代码部分参考了B站尚硅谷教程中的实现，因此实现思路与Python部分不同，但是算法的基本思想是一致的。
public class HeapSort {
public static void heapSort(int[] data) {
int arrayLength = data.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
buildMaxdHeap(data, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(data, 0, arrayLength - 1 - i);
}
}
// 对data数组从0到lastIndex建大顶堆
private static void buildMaxdHeap(int[] data, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存当前正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex +1
// 代表k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 如果右子节点的值较大
if (data[biggerIndex] - data[biggerIndex + 1] < 0) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大子节点的值
if (data[k] - data[biggerIndex] < 0) {
// 交换它们
swap(data, k, biggerIndex);
// 将biggerIndex赋给k，开始while循环的下一次循环
// 重新保证k节点的值大于其左、右节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
// 交换data数组中i、j两个索引处的元素
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
int[] data = {1, 2, 3, 7, 6, -1, 0, 8, 5, 4};
heapSort(data);
System.out.println(java.util.Arrays.toString(data));
}
}
运行结果：
