一，直接插入排序
//直接插入排序的算法时间复杂度分析： //如果输入为正序，则每次比较一次就可以找到元素最终位置，复杂度为O(n) //如果输入为反序，则每次要比较i个元素，复杂度为O(n2) //平均时间复杂度为O(n2) public static void straigthInsertSort(int[] num) { int n = num.length; for(int i = 1;i < n;i++)//从第二个开始向前插入 { int x = num[i]; int j; for(j = i - 1;j >= 0&&num[j] > x;j--) { num[j + 1] = num[j]; } num[j + 1] = x; print(num); } } // 5 2 2 3 6 2 0 8 9 9 // 2 5 2 3 6 2 0 8 9 9 // 2 2 5 3 6 2 0 8 9 9 // 2 2 3 5 6 2 0 8 9 9 // 2 2 3 5 6 2 0 8 9 9 // 2 2 2 3 5 6 0 8 9 9 // 0 2 2 2 3 5 6 8 9 9 // 0 2 2 2 3 5 6 8 9 9 // 0 2 2 2 3 5 6 8 9 9 // 0 2 2 2 3 5 6 8 9 9
二，希尔排序
//希尔排序的时间负责度与增量的选取有关，每次折半的增量选取时间复杂度为O(n2),最佳时间复杂度为O(nlogn) //希尔排序没有快排快，中等规模条件下表现较好，大规模情况下不如快排 //快排在最坏情况下表现极差，而希尔在最坏情况下和平均情况表现差不多 //希尔每趟排序会让序列变得更加有序，虽然下一趟元素个数增多，但是需要移动的增加并不是很多，因此效率比直接插入高很多 //希尔排序适合于大多数情况 public static void ShellSort(int[] num) { int n = num.length; int d = n; while(d != 1) { d = d / 2; for(int x = 0;x < d;x++) { for(int i = x + d;i < n;i = i + d) { int tmp = num[i]; int j; for(j = i - d;j >= 0&&num[j] > tmp;j = j - d) num[j + d] = num[j]; num[j + d] = tmp; } } print(num); } } // 6 8 8 5 5 1 1 2 0 8 // 1 1 2 0 5 6 8 8 5 8 // 1 0 2 1 5 6 5 8 8 8 // 0 1 1 2 5 5 6 8 8 8
三，选择排序
//选择排序的时间复杂度是O(n2) //因为需要进行数据的交换操作，所以选择排序算法是不稳定的 //选择排序每趟结束都有一个元素在最终位置上 public static void selectSort(int[] num) { int n = num.length; for(int i = 0;i < n;i++) { int cur = num[i]; int key = i;//最小值的索引 for(int j = i + 1;j < n;j++) if(num[j] < num[key]) key = j; if(key != i) { num[i] = num[key]; num[key] = cur; } print(num); } } // 0 6 1 0 9 4 8 0 2 3 // 0 6 1 0 9 4 8 0 2 3 // 0 0 1 6 9 4 8 0 2 3 // 0 0 0 6 9 4 8 1 2 3 // 0 0 0 1 9 4 8 6 2 3 // 0 0 0 1 2 4 8 6 9 3 // 0 0 0 1 2 3 8 6 9 4 // 0 0 0 1 2 3 4 6 9 8 // 0 0 0 1 2 3 4 6 9 8 // 0 0 0 1 2 3 4 6 8 9 // 0 0 0 1 2 3 4 6 8 9
四，冒泡排序
//冒泡排序的时间复杂度为O(n2) //冒泡排序上稳定的算法 //每趟结束都有一个元素在最终位置上 public static void bubbleSort(int[] num) { int n = num.length; for(int i = 0;i < n - 1;i++) { for(int j = 0;j < n - i - 1;j++) { if(num[j] > num[j + 1]) { int tmp = num[j]; num[j] = num[j + 1]; num[j + 1] = tmp; } } print(num); } } // 4 0 8 3 4 2 9 7 8 4 // 0 4 3 4 2 8 7 8 4 9 // 0 3 4 2 4 7 8 4 8 9 // 0 3 2 4 4 7 4 8 8 9 // 0 2 3 4 4 4 7 8 8 9 // 0 2 3 4 4 4 7 8 8 9 // 0 2 3 4 4 4 7 8 8 9 // 0 2 3 4 4 4 7 8 8 9 // 0 2 3 4 4 4 7 8 8 9 // 0 2 3 4 4 4 7 8 8 9
五，快速排序
//快排的时间复杂度为O(nlogn) //当n较大时用快排比较好，当序列基本有序时，用快排反而不太好 //快排是不稳定的 //快排被认为是相同时间复杂度下平均性能最好的排序算法 public static void quickSort(int[] num) { quick(num,0,num.length - 1); } private static void quick(int[] num,int low,int high) { if(low < high)//! { int mid = partition(num, low, high); print(num); quick(num,low,mid - 1); quick(num,mid + 1,high); } } private static int partition(int[] num,int low,int high) { int temp = num[low]; while(low < high) { while(num[high] >= temp&&high > low) high--; num[low] = num[high]; while(num[low] <= temp&&high > low) low++; num[high] = num[low]; } num[low] = temp; return low; } // 3 2 6 5 8 4 6 9 2 2 // 2 2 2 3 8 4 6 9 5 6 // 2 2 2 3 8 4 6 9 5 6 // 2 2 2 3 8 4 6 9 5 6 // 2 2 2 3 6 4 6 5 8 9 // 2 2 2 3 5 4 6 6 8 9 // 2 2 2 3 4 5 6 6 8 9
六，堆排序
//堆排序的时间复杂度是O(nlogn) //堆排序是不稳定的排序算法 //由于初始建堆时比较的次数较多，所以堆排序不适合于记录较少的情况 public static void heapSort(int[] num) { int n = num.length; for(int i = (n - 1) / 2;i >= 0;i--) heapAdjust(num, i, n); for(int i = 0;i < n;i++) { int tmp = num[0]; num[0] = num[n - 1 - i]; num[n - 1 - i] = tmp; print(num); heapAdjust(num, 0, n - 1 - i); } } private static void heapAdjust(int[] num,int s,int size) { int tmp = num[s]; int child; while(s < size) { child = s * 2 + 1; if(child < size - 1&&num[child] < num[child + 1]) child++; if(child >= size||num[s] > num[child]) break; num[s] = num[child]; s = child; num[child] = tmp; } } // 5 7 7 6 0 6 4 0 1 4 // 0 6 7 5 4 6 4 0 1 7 // 1 6 6 5 4 0 4 0 7 7 // 0 5 6 1 4 0 4 6 7 7 // 0 5 4 1 4 0 6 6 7 7 // 0 4 4 1 0 5 6 6 7 7 // 0 1 4 0 4 5 6 6 7 7 // 0 1 0 4 4 5 6 6 7 7 // 0 0 1 4 4 5 6 6 7 7 // 0 0 1 4 4 5 6 6 7 7 // 0 0 1 4 4 5 6 6 7 7
七，归并排序
//归并排序是稳定的排序算法
//归并排序的时间复杂度是O(nlogn)
//归并排序的速度仅次于快速排序，适用于总体无序但个子项相对有序的情况
public static void mergeSort(int[] num)
{
int n = num.length - 1;
mergeRecursive(num, 0, n);
}
private static void mergeRecursive(int[] num,int left,int right)
{
if(left < right)
{
int middle = (left + right) / 2;
mergeRecursive(num, left, middle);
mergeRecursive(num, middle + 1, right);
merge(num,left,middle,right);
}
}
private static void merge(int[] num,int left,int middle,int right)
{
int[] tmp = new int[num.length];
int mid = middle + 1;
int index = left;
int originLeft = left;
while(left <= middle&&mid <= right)
{
if(num[left] < num[mid])
tmp[index++] = num[left++];
else
tmp[index++] = num[mid++];
}
while(left <= middle)
tmp[index++] = num[left++];
while(mid <= right)
tmp[index++] = num[mid++];
while(originLeft <= right)
num[originLeft] = tmp[originLeft++];
print(num);
}
// 5 7 7 8 2 0 5 0 3 4
// 5 7 7 8 2 0 5 0 3 4
// 5 7 7 8 2 0 5 0 3 4
// 5 7 7 2 8 0 5 0 3 4
// 2 5 7 7 8 0 5 0 3 4
// 2 5 7 7 8 0 5 0 3 4
// 2 5 7 7 8 0 0 5 3 4
// 2 5 7 7 8 0 0 5 3 4
// 2 5 7 7 8 0 0 3 4 5
// 0 0 2 3 4 5 5 7 7 8