排序算法
排序算法
1、冒泡排序
冒泡排序是一种非常直接，但是性能比较低的排序方法，其时间复杂度为$\mathcal{O}{n^2}$，它通过两两比较数组中的元素，若第一个元素大于第二个元素，则将两个元素交换位置，逐步将元素中的最大值归位。其排序过程如下图所示：
C++代码如下：
template<typename T>
void bubble_sort(vector<T> array)
{
int size = array.size();
for(int i = 0;i < size - 1; i++)
{
for(int j = 0;j < size-1-i; j++)
{
if(array[j]>array[j+1])
swap(array[j].array[j+1]);
}
}
}
python代码如下：
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
2、选择排序
选择排序是通过查找未排序部分的最小值，然后将其与第一个未排序的元素进行交换的过程，也就是通过遍历数组，将其每个未排序的位置与未排序部分的最小值进行交换，也就得到了一个从小到大排序的数组，时间复杂度也为$\mathcal{O}{n^2}$其过程如下图所示：
C++代码：
template<typename T>
void selection_sort(vector<T>& arr)
{
int size = arr.size();
for (int i = 0; i < arr.size() - 1; i++)
{
int min_index = i;
for (int j = i + 1; j < arr.size(); j++)
{
if (arr[j] < arr[min_index])
min_index = j;
}
swap(arr[i], arr[min_index]);
}
}
python代码：
def selectionSort(arr):
for i in range(len(arr) - 1):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
3、插入排序
我们将一个数组分为已排序子数组和未排序子数组，在一开始，一个初始数组的已排序子数组只包含原始数组的第一个元素，插入排序通过将未排序数组的第一个元素插入到已排序子数组中的合适位置来达到排序的目的，时间复杂度为$\mathcal{O}{n^2}$，其排序过程如下图所示：
C++代码：
template<typename T>
void insertion_sort(vector<T>& array)
{
int size = array.size();
for (int i = 1; i < size; i++)
{
int temp = array[i];
int j = i - 1;
for (; j >= 0; j--)
{
if (array[j] > temp)
array[j + 1] = array[j];
else
break;
}
array[j+1] = temp;
}
}
python代码：
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
4、归并排序
归并排序首先将初始数组分为两个大致相等的部分，若数组有奇数个元素，则其中一半比另一半多一个元素，子数组再以上述过程分成两部分，直到每个数组只有一个元素，之后再将两两数组合并成一个数组，合并的过程中将两数组以从小到大的顺序进行排列，直到最后将所有子数组合并成一个单一的数组，其时间复杂度为$\mathcal{O}(n \ log_{}\ n)$，排序过程如下图所示：
C++代码：
void merge(vector<int>& array, int start, int end) //合并函数
{
if (start == end)
return;
int mid = (start + end) / 2;
merge(array, start, mid);
merge(array, mid + 1, end);
vector<int> res;
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) //合并两个数组
{
if (array[i] <= array[j])
{
res.push_back(array[i]);//按从小到大存放在res数组里面
i++;
}
else
{
res.push_back(array[j]);
j++;
}
}
while (i <= mid) // j 序列结束，将剩余的 i 序列补充在res数组中
{
res.push_back(array[i]);
i++;
}
while (j <= end)// i 序列结束，将剩余的 j 序列补充在res数组中
{
res.push_back(array[j]);
j++;
}
k = 0; //从小标为 0 开始传送
for (int i = start; i <= end; i++) //将res数组的值传递给数组array
{
array[i] = res[k++];
}
}
void mergesort(vector<int>& a) //归并排序
{
merge(a, 0, a.size() - 1);
}
python代码：
# 归并排序
def merge_sort(num_list):
length = len(num_list)
# 递归终止退出条件
if length <= 1:
return num_list
# 拆分
mid = length // 2
left_l = merge_sort(num_list[:mid]) # 对左侧的列表进行排序
right_l = merge_sort(num_list[mid:]) # 对右侧的列表进行排序
# merge 合并操作
# 初始化两个指针p, q 初始位置为起始位置，初始化一个临时数组temp_list
p, q, temp_list = 0, 0, list()
len_left, len_right = len(left_l), len(right_l) # 计算当前被合并的列表的长度
while len_left > p and len_right > q:
if left_l[p] <= right_l[q]:
temp_list.append(left_l[p])
p += 1
else:
temp_list.append(right_l[q])
q += 1
# 如果left 和 right 的长度不相等，把长的部分直接追加到列表中
temp_list += left_l[p:]
temp_list += right_l[q:]
return temp_list
if __name__ == '__main__':
num_list = [44, 23, 1, 14, 6, 9, 4, 5, 33]
new_list = merge_sort(num_list)
for k, v in enumerate(new_list):
num_list[k] = v
print('num_list:', num_list)