冒泡排序
介绍：
冒泡排序是重复地走访要排序的数组，每一次只比较两个元素，如果顺序错误就交换两个元素的位置。当重复到没有需要交换的元素时，排序完成。
代码实现
#Python
def bubble_sort(list):
count=len(list)
for i in range(0,count):
for j in range(i+1,count):
if list[i]>list[i+1]:
list[i],list[i+1]=list[i+1],list[i]
return list
//Java
public static int[] bubble_sort(int[] list) {
for(int i=1;i<list.length;i++) {
for(int j=0;j<list.length-i;j++) {
if(list[j]>list[j+1]) {
int temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
}
}
return list;
}
快速排序
介绍：
通过一次排序将需要排序的数据分为两个部分，其中一个部分的数据都比另一部分所有数据小，然后在按这个方法将两个部分的数据分别进行快速排序。整个排序过程使用递归来将整个数据变成有序序列。
代码实现
#Python
def quick_sort(list,left,right):
#left和right为列表索引下表
if left>=right:
return list
key=list[left]
low=left
high=right
while left<right:
while left<right and list[right]>=key:
right-=1
list[left]=list[right]
while left<right and list[left]<=key:
left+=1
list[right]=list[left]
list[right]=key
quick_sort(list,low,right-1)
quick_sort(list,left+1,high)
return list
//Java
public static void quick_sort(int a[], int low, int high) {
int i, j, index;
if (low > high) {
return;
}
i = low;
j = high;
index = a[i]; // 用子表的第一个记录做基准
while (i < j) { // 从表的两端交替向中间扫描
while (i < j && a[j] >= index)
j--;
if (i < j)
a[i++] = a[j];// 用比基准小的记录替换低位记录
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基准大的记录替换高位记录
a[j--] = a[i];
}
a[i] = index;// 将基准数值替换回 a[i]
quick_sort(a, low, i - 1); // 对低子表进行递归排序
quick_sort(a, i + 1, high); // 对高子表进行递归排序
}
插入排序
介绍：
插入排序的基本操作就是讲一个数据插入到已经排好序的有序数据中，从而得到一个新的、length加一的有序数列。插入算法吧要排序的数据分为两部分：第一部分包含了这组数据除最后一个元素的的所有元素，第二部分就是需要插入的元素。在第一部分排序完成后，将第二部分的元素插入到已经排好序的第一部分中。
代码实现
#Python
def insert_sort(list):
count=len(list)
for i in range(1,count):
key=list[i]
j=i-1
while j>=0:
if list[j]>key:
list[j+1]=list[j]
list[j]=key
j-=1
return list
//Java
public static void insert_sort(int[] arr)
{
int i, j;
int n = arr.Length;
int target;
//假定第一个元素被放到了正确的位置上
//这样，仅需遍历1 - n-1
for (i = 1; i < n; i++)
{
j = i;
target = arr[i];
while (j > 0 && target < arr[j - 1])
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
}
希尔排序
介绍：
希尔排序是插入排序的一种。也称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序算法是一种非稳定排序算法。希尔排序是吧记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量减少，每组包含的关键词增多，当增量减至1时，整个文件恰好被分为一组。
代码实现
#Python
def shell_sort(list):
length=len(list)
inc=0
#选用Knuth在1969年提出的步长序列：1 4 13 40 121 364 1093 3280 。。。
while inc<=length/3:
inc=inc*3+1
print(inc)
while inc>=1:
for i in range(inc,length):
tmp=list[i]
for j in range(i,0,-inc):
if tmp<list[j-inc]:
list[j]=list[j-inc]
else:
j+=inc
break
list[j-inc]=tmp
inc//=3
//Java
public static void shell_sort(int[] list) {
int j = 0;
int temp = 0;
for (int increment = list.length / 2; increment > 0; increment /= 2) {
System.out.println("increment:" + increment);
for (int i = increment; i < list.length; i++) {
// System.out.println("i:" + i);
temp = list[i];
for (j = i - increment; j >= 0; j -= increment) {
if (temp < data[j]) {
list[j + increment] = list[j];
} else {
break;
}
}
list[j + increment] = temp;
}
for (int i = 0; i < data.length; i++)
System.out.print(list[i] + " ");
}
}
Java的希尔排序参考的CSDN
