1. 直接插入排序
思想: 每次将一个待排序的数据按照其关键字的大小插入到前面已经排序好的数据中的适当位置, 直到全部数据排序完成时间复杂度: O(n2) O(n) O(n2) (最坏 最好 平均)空间复杂度: O(1)稳定性: 稳定 每次都是在前面已排好序的序列中找到适当的位置, 只有小的数字会往前插入, 所以原来相同的两个数字在排序后相对位置不变代码:
- /**
- * 直接插入排序
- * @param array
- */
- public static void insertSort(int [] array){
- if(array==null)
- return ;
- for(int i=1;i<array.length;i++){
- int temp=array[i];
- int j=i-1;
- while(j>=0&&array[j]>temp){
- array[j+1]=array[j];
- --j;
- }
- array[j+1]=temp;
- }
- }
2. 希尔排序
思想: 希尔排序根据增量值对数据按下表进行分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整体采用直接插入排序得到有序数组, 算法终止时间复杂度: O(n2) O(n) O(n1.5) (最坏, 最好, 平均)空间复杂度: O(1)稳定性: 不稳定 因为是分组进行直接插入排序, 原来相同的两个数字可能会被分到不同的组去, 可能会使得后面的数字会排到前面, 使得两个相同的数字排序前后位置发生变化不稳定举例: 4 3 3 2 按 2 为增量分组, 则第二个 3 会跑到前面代码:
- /**
- * 希尔排序
- * @param array
- */
- public static void shellSort(int[] array) {
- if (array == null) return;
- int len = array.length / 2;
- while (len >= 1) {
- for (int i = len; i < array.length; i++) {
- int temp = array[i];
- int j = i - len;
- while (j >= 0 && array[j] > temp) {
- array[j + len] = array[j];
- j -= len;
- }
- array[j + len] = temp;
- }
- len -= 1;
- }
- }
3. 冒泡排序
思想: 对待排序元素的关键字从后往前进行多遍扫描, 遇到相邻两个关键字次序与排序规则不符时, 就将这两个元素进行交换这样关键字较小的那个元素就像一个泡泡一样, 从最后面冒到最前面来时间复杂度: 最坏: O(n2) 最好: O(n) 平均: O(n2)空间复杂度: O(1)稳定性: 稳定, 相邻的关键字两两比较, 如果相等则不交换所以排序前后的相等数字相对位置不变代码:
- /**
- * 冒泡排序
- * @param array
- */
- public static void bubbleSort(int[] array) {
- if (array == null) return;
- boolean isChange = false;
- int len = array.length;
- for (int i = 0; i < len; i++) {
- for (int j = len - 1; j > i; j--) {
- if (array[j] < array[j - 1]) {
- int temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- isChange = true;
- }
- }
- if (!isChange) return;
- isChange = false;
- }
- }
4. 快速排序
思想: 该算法是分治算法, 首先选择一个基准元素, 根据基准元素将待排序列分成两部分, 一部分比基准元素小, 一部分大于等于基准元素, 此时基准元素在其排好序后的正确位置, 然后再用同样的方法递归地排序划分的两部分基准元素的选择对快速排序的性能影响很大, 所有一般会想打乱排序数组选择第一个元素或则随机地从后面选择一个元素替换第一个元素作为基准元素时间复杂度: 最坏: O(n2) 最好: O(nlogn) 平均: O(nlogn)空间复杂度: O(nlogn)用于方法栈稳定性: 不稳定 快排会将大于等于基准元素的关键词放在基准元素右边, 加入数组 1 2 2 3 4 5 选择第二个 2 作为基准元素, 那么排序后 第一个 2 跑到了后面, 相对位置发生变化代码:
- /**
- * 快速排序
- * @param array
- */
- public static void quickSort(int [] array){
- if(array==null)
- return ;
- int len=array.length;
- quickSort(array, 0, len-1);
- }
- private static void quickSort(int [] array,int start,int end){
- if(start>=end)
- return ;
- int temp=array[start];
- int l=start,r=end;
- while(l<r){
- while(array[r]>temp&&l<r)
- --r;
- array[l]=array[r];
- while(array[l]<=temp&&l<r)
- ++l;
- array[r]=array[l];
- }
- array[l]=temp;
- quickSort(array,start,l-1);
- quickSort(array,l+1,end);
- }
5. 直接选择排序
思想: 首先在未排序序列中找到最小 (大) 元素, 存放到排序序列的起始位置, 然后每次从剩余未排序元素中继续寻找最小 (大) 元素放到已排序序列的末尾以此类推, 直到所有元素均排序完毕时间复杂度: 最坏: O(n2) 最好: O(n2) 平均: O(n2)空间复杂度: O(1)稳定性: 不稳定 例如数组 2 2 1 3 第一次选择的时候把第一个 2 与 1 交换使得两个 2 的相对次序发生了改变代码:
- /**
- * 选择排序
- * @param array
- */
- public static void selectSort(int[] array) {
- if (array == null) return;
- int len = array.length;
- int minIndex;
- for (int i = 0; i < len; i++) {
- minIndex = i;
- for (int j = i + 1; j < len; j++) {
- if (array[minIndex] > array[j]) {
- minIndex = j;
- }
- }
- int temp = array[i];
- array[i] = array[minIndex];
- array[minIndex] = temp;
- }
- }
6. 堆排序
思想: 堆排序是利用堆的性质进行的一种选择排序, 先将排序元素构建一个最大堆, 每次堆中取出最大的元素并调整堆将该取出的最大元素放到已排好序的序列前面这种方法相对选择排序, 时间复杂度更低, 效率更高时间复杂度: 最坏: O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)空间复杂度: O(1)稳定性: 不稳定 例如 5 10 15 10 如果堆顶 5 先输出, 则第三层的 10(最后一个 10)的跑到堆顶, 然后堆稳定, 继续输出堆顶, 则刚才那个 10 跑到前面了, 所以两个 10 排序前后的次序发生改变代码:
- /**
- * 堆排序 最大堆
- * @param array
- */
- public static void heapSort(int [] array){
- if(array==null)
- return;
- int N=array.length-1;
- for(int i=N/2-1;i>=0;i--){
- heapSort(i,array,N);
- }
- while(N>0){
- swap(0, N, array);
- heapSort(0,array,--N);
- }
- }
- private static void heapSort(int n,int[] array,int N){
- while(n*2+1<=N){
- int k=n*2+1;
- if(k<N&&array[k]<array[k+1]){
- ++k;
- }
- if(array[n]>=array[k])
- break;
- swap(n, k, array);
- n=k;
- }
- }
7. 归并排序
思想: 归并排序采用了分治算法, 首先递归将原始数组划分为若干子数组, 对每个子数组进行排序然后将排好序的子数组递归合并成一个有序的数组时间复杂度: 最坏: O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)空间复杂度: O(n)稳定性: 稳定代码:
- /**
- * 归并排序
- * @param array
- */
- public static void mergeSort(int [] array){
- if(array==null)
- return;
- mergeSort(array, 0, array.length-1);
- }
- private static void mergeSort(int [] array,int start,int end){
- if(start>=end){
- return;
- }
- int mid=(start+end)/2;
- mergeSort(array, start, mid);
- mergeSort(array, mid+1, end);
- merge(array, start, mid, end);
- }
- private static void merge(int [] array,int start,int mid,int end){
- int [] temps=new int[end-start+1];
- int l1=start,l2=mid+1;
- int i=0;
- while(l1<=mid&&l2<=end){
- if(array[l1]>array[l2])
- temps[i++]=array[l2++];
- else
- temps[i++]=array[l1++];
- }
- while(l1<=mid)
- temps[i++]=array[l1++];
- while(l2<=end)
- temps[i++]=array[l2++];
- for(i=0;i<=end-start;i++)
- array[i+start]=temps[i];
- }
来源: http://blog.csdn.net/z956281507/article/details/79271708