1.冒泡排序(bubble sort)

image

def short_bubble_sort(a_list):
exchanges = True
pass_num = len(a_list) - 1
while pass_num > 0 and exchanges:
exchanges = False
for i in range(pass_num):
if a_list[i] > a_list[i + 1]:
exchanges = True
a_list[i],a_list[i+1] = a_list[i+1], a_list[i]
pass_num = pass_num - 1

if __name__ == '__main__':
a_list=[20, 40, 30, 90, 50, 80, 70, 60, 110, 100]
short_bubble_sort(a_list)
print(a_list)

2.选择排序(selection sort)

image

def selection_sort(a_list):
for fill_slot in range(len(a_list) - 1, 0, -1):
pos_of_max = 0
for location in range(1, fill_slot + 1):
if a_list[location] > a_list[pos_of_max]:
pos_of_max = location
a_list[fill_slot],a_list[pos_of_max]=a_list[pos_of_max],a_list[fill_slot]

a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

3.插入排序(insertion sort)

image

def insertion_sort(a_list):
for index in range(1, len(a_list)):
current_value = a_list[index]
position = index
while position > 0 and a_list[position - 1] > current_value:
a_list[position] = a_list[position - 1]
position = position - 1
a_list[position] = current_value

def insertion_sort_binarysearch(a_list):
for index in range(1, len(a_list)):
current_value = a_list[index]
position = index
low=0
high=index-1
while low<=high:
mid=(low+high)/2
if a_list[mid]>current_value:
high=mid-1
else:
low=mid+1
while position > low:
a_list[position] = a_list[position - 1]
position = position -1
a_list[position] = current_value

a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)

4.合并排序(merge sort)

image

image

def merge_sort(a_list):
print("Splitting ", a_list)
if len(a_list) > 1:
mid = len(a_list) // 2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=0;j=0;k=0;
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
a_list[k] = left_half[i]
i=i+1
else:
a_list[k] = right_half[j]
j=j+1
k=k+1
while i < len(left_half):
a_list[k] = left_half[i]
i=i+1
k=k+1
while j < len(right_half):
a_list[k] = right_half[j]
j=j+1
k=k+1
print("Merging ", a_list)

a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(a_list)
print(a_list)

[下面使用的是C++来实现的，合并排序的代码格式类似算法导论中的伪代码]

#include <iostream>
using namespace std;

int calculateInversions(int arr[], int p, int r);
int mergeInversions(int arr[], int p, int q, int r);

int main(int argc, const char * argv[])
{
int arr[] = {2,3,8,6,1};
int count = calculateInversions(arr, 0, 4);
cout << "count inversions : " << count << endl;
return 0;
}

int calculateInversions(int arr[], int p, int r) {
int count=0;
if(p < r) {
int q = (p + r) / 2;
count += calculateInversions(arr, p, q);
count += calculateInversions(arr, q+1, r);
count += mergeInversions(arr, p, q, r);
}
return count;
}

int mergeInversions(int arr[], int p, int q, int r){
int count=0;
int n1=q-p+1, n2=r-q;
int left[n1+1], right[n2+1];
for (int i=0; i<n1; i++) {
left[i]=arr[p+i];
}
for (int j=0; j<n2; j++) {
right[j]=arr[q+1+j];
}
left[n1]=INT32_MAX;
right[n2]=INT32_MAX;
int i=0, j=0;
for (int k=p; k<=r; k++) {
if (left[i]<=right[j]) {
arr[k]=left[i];
i++;
}else{
arr[k]=right[j];
count += n1-i;
j++;
}
}
return count;
}