Java数据结构十大排序
wwzzzzzzzzzzzzz 人气:01.直接插入排序
1.1 动图演示
1.2 插入排序的思路
- 从第一个元素开始,这里我们第一个元素是已排序的.
- 取下一个元素,和有序序列的元素从后往前比较.( 有序区间 : [0,i) )
- 如果得到的有序序列的元素 比 该元素大 则 将取得的有序元素往后放
- 重复3操作,直到得到的有序元素 比 该元素小, 或者 有序元素比完了.记录这个位置
- 然后将该元素放入到这个位置.
- 遍历数组,重复2~5的操作.
1.3 代码实现
/** * 时间复杂度: * 最好的情况: O(n) * 最坏的情况: O(n^2) * 空间复杂度: O(1) * @param array */ public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int j = i - 1; int tmp = array[i]; while (j >= 0) { if (array[j] > tmp) { array[j + 1] = array[j]; j--; }else { break; } } array[j + 1] = tmp; } }
1.4 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
插入排序,初始数据越接近有序,时间效率越高。
2.希尔排序
2.1 原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有记录分成个gap组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取gap = (gap/3)+1
,重复上述分组和排序的工作。当到达gap=1时,所有记录在统一组内排好序。
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
2.2 动图演示
2.3 代码实现
/** * * @param array 排序的数组 * @param gap 每组的间隔 -> 数组 */ public static void shell(int[] array,int gap){ for (int i = gap; i < array.length ; i++) { int tmp = array[i]; int j = i - gap; while(j>=0){ if(array[j] > tmp){ array[j + gap] = array[j]; j -= gap; }else { break; } } array[j + gap] = tmp; } } public static void shellSort(int[] array){ int gap = array.length; while (gap > 1){ gap = (gap / 3) + 1;// +1 保证最后一个序列是 1 (除几都行) shell(array,gap); } }
2.4 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^1.3) | O(n^2) | O(n) | O(1) | 不稳定 |
3.直接选择排序
3.1 动图演示
3.2 代码实现
/** * 时间复杂度: * 最好: O(n^2) * 最坏: O(n^2) * 空间复杂度: O(1) * 稳定性: 不稳定 * @param array */ public static void selectSort(int[] array){ for (int i = 0; i < array.length - 1; i++) { for (int j = i + 1; j <array.length ; j++) { if(array[j] < array[i]){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } }
3.3 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
4.堆排序
4.1 动图演示
4.2 代码实现
public static void siftDown(int[] array,int root, int len){ int parent = root; int child = root * 2 + 1; while (child < len){ if( child+1 < len && array[child] < array[child+1] ){ child++; } //这里child下标就是左右孩子的最大值的下标 if(array[child] > array[parent]){ int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = parent * 2 + 1; }else { break; } } } public static void createHeap(int[] array){ for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) { siftDown(array,i,array.length); } } public static void heapSort(int[] array){ createHeap(array); int end = array.length - 1; while (end > 0){ int tmp = array[end]; array[end] = array[0]; array[0] =tmp; siftDown(array,0,end); end--; } }
4.3 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
5.冒泡排序
5.1 动图演示
5.2 代码实现
public static void BubbleSort(int[] array){ for (int i = 0; i < array.length - 1; i++) { boolean flg = false; for (int j = 0; j < array.length - 1 - i ; j++) { if(array[j+1] < array[j]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flg = true; } } if(!flg){ break; } } }
5.3 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
6.快速排序
6.1 原理
- 从待排序区间选择一个数,作为基准值(pivot);
- Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基准值大的(可以包含相等的)放到基准值的右边;
- 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1,代表已经有序,或者小区间的长度 == 0,代表没有数据。
6.2 动图演示
6.3 实现方法
6.3.1 Hoare法
6.3.2 挖坑法
6.4 代码实现
//Hoare法 public static void swap(int[] array,int i,int j){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static int partition1(int[] array,int low,int high) { int i = low; int tmp = array[low]; while (low < high){ while (low < high && array[high] >= tmp){ high--; } while (low < high && array[low] <= tmp){ low++; } swap(array,low,high); } swap(array,i,low); return low; } //挖坑法 public static int partition2(int[] array,int low,int high) { int tmp = array[low]; while (low < high){ while (low < high && array[high] >= tmp){ high--; } array[low] = array[high]; while (low < high && array[low] <= tmp){ low++; } array[high] = array[low]; } array[low] = tmp; return low; } public static void quick(int[] array,int start,int end){ if(start >= end) return; int pivot = partition1(array,start,end); quick(array,start,pivot-1); quick(array,pivot+1,end); } public static void quickSort(int[] array){ quick(array,0,array.length-1); }
6.5 快排优化
6.5.1 三数取中法
public static void swap(int[] array,int i,int j){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static int partition2(int[] array,int low,int high) { int tmp = array[low]; while (low < high){ while (low < high && array[high] >= tmp){ high--; } array[low] = array[high]; while (low < high && array[low] <= tmp){ low++; } array[high] = array[low]; } array[low] = tmp; return low; } public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){ if(array[mid] > array[start]){ swap(array,start,mid); }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start] if(array[mid] > array[end]){ swap(array,mid,end); }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end] if(array[start] > array[end]){ swap(array,start,end); }//此时有 array[mid] <= array[start] <= array[end] } public static void quick1(int[] array,int start,int end){ if(start >= end) return; int mid = (start + end) / 2; selectPivotMedianOFThree(array,start,end,mid); int pivot = partition2(array,start,end); quick1(array,start,pivot-1); quick1(array,pivot+1,end); } public static void quick1Sort(int[] array){ quick1(array,0,array.length - 1); }
6.5.2 加上直接插入排序
public static void swap(int[] array,int i,int j){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void insertSort2(int[] array,int start,int end){ for (int i = start + 1; i <= end; i++) { int j = i + 1; int tmp = array[i]; while (j >= 0){ if(array[j] > tmp){ array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } } public static int partition2(int[] array,int low,int high) { int tmp = array[low]; while (low < high){ while (low < high && array[high] >= tmp){ high--; } array[low] = array[high]; while (low < high && array[low] <= tmp){ low++; } array[high] = array[low]; } array[low] = tmp; return low; } public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){ if(array[mid] > array[start]){ swap(array,start,mid); }//此时mid下标的值肯定小于start下标的值 array[mid] <= array[start] if(array[mid] > array[end]){ swap(array,mid,end); }//此时mid下标的值肯定小于end下标的值 array[mid] <= array[end] if(array[start] > array[end]){ swap(array,start,end); }//此时有 array[mid] <= array[start] <= array[end] } public static void quick2(int[] array,int start,int end){ if(start >= end) return; if(end - start + 1 <= 100){ insertSort2(array,start,end); return; } int mid = (start + end)/2; selectPivotMedianOFThree(array,start,end,mid); int pivot = partition2(array,start,end); quick2(array,start,pivot-1); quick2(array,pivot+1,end); } public static void quick2Sort(int[] array){ quick2(array,0,array.length - 1); }
6.6 非递归的实现
6.6.1 非递归思路
- 首先调用partition,找到pivot
- 然后把pivot的 左区间 和 右区间 的下标放到栈立马
- 判断栈是否为空,不为空,弹出栈顶的2个元素(注意:入栈的顺序 决定了出栈的顺序中的第一个元素是high的还是low的)
- 然后再进行调用partition,找pivot,
- 重复以上操作.
6.6.2 非递归代码实现
public static void quickSort4(int[] array){ Stack<Integer> stack = new Stack<>(); int low = 0; int high = array.length - 1; int pivot = partition2(array,low ,high); //左边有2个元素即以上 if(pivot > low + 1){ stack.push(0); stack.push(pivot - 1); } //右边有2个元素即以上 if(pivot < high - 1){ stack.push(pivot + 1); stack.push(high); } while (!stack.isEmpty()){ high = stack.pop(); low = stack.pop(); pivot = partition2(array,low,high); //左边有2个元素即以上 if(pivot > low + 1){ stack.push(0); stack.push(pivot - 1); } //右边有2个元素即以上 if(pivot < high - 1){ stack.push(pivot + 1); stack.push(high); } } }
6.7 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n^2) | O(n * log(n)) | O(log(n))~O(n) | 不稳定 |
7.归并排序
7.1 原理
归并排序(MERGE-SORT
)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer
)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子 序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
7.2 动图演示
7.3 代码实现—递归
public static void merge(int[] array,int low ,int high ,int mid){ int s1 = low; int e1 = mid; int s2 = mid+1; int e2 = high; int[] tmp = new int[high - low + 1]; int k = 0; while (s1 <= e1 && s2 <= e2){ if(array[s1] <= array[s2]){ tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 <= e1){ tmp[k++] = array[s1++]; } while (s2 <= e2){ tmp[k++] = array[s2++]; } for (int i = 0; i < tmp.length; i++) { array[i+low] = tmp[i]; } } public static void mergeSortInternal(int[] array,int low ,int high){ if(low >= high) return; int mid = (low + high) / 2; mergeSortInternal(array,low,mid); mergeSortInternal(array,mid+1,high); merge(array,low,high,mid); } public static void mergeSort(int[] array){ mergeSortInternal(array,0,array.length - 1); }
7.4 代码实现—非递归
public static void merge1(int[] array,int gap){ int[] tmp = new int[array.length]; int k = 0; int s1 = 0; int e1 = s1 + gap - 1; int s2 = e1 + 1; int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1; while (s2 < array.length){ while (s1 <= e1 && s2 <= e2){ if(array[s1] <= array[s2]){ tmp[k++] = array[s1++]; }else { tmp[k++] = array[s2++]; } } while (s1 <= e1){ tmp[k++] = array[s1++]; } while (s2 <= e2){ tmp[k++] = array[s2++]; } s1 = e2 + 1; e1 = s1 + gap - 1; s2 = e1 + 1; e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1; } while (s1 <= array.length - 1){ tmp[k++] = array[s1++]; } for (int i = 0; i < tmp.length; i++) { array[i] = tmp[i]; } } public static void mergeSort1(int[] array){ for (int i = 1; i < array.length; i*=2) { merge1(array,i); } }
7.5 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
8.计数排序
当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
8.1 算法的步骤
(1)找出待排序的数组中最大和最小的元素
(2)统计数组中每个值为i的元素出现的次数,存入数组C的第i项
(3)对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
(4)反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
8.2 动图演示
8.3 代码实现
public static void CountingSort(int[] array){ int maxValue = GetMaxValue(array); int bucketLen = maxValue + 1; int[] bucket = new int[bucketLen]; for (int value:array) { bucket[value]++; } int index = 0 ; for (int i = 0; i < bucketLen; i++) { while(bucket[i] > 0){ array[index++] = i; bucket[i]--; } } } public static int GetMaxValue(int[] array){ int maxValue = array[0]; for (int i = 0; i < array.length; i++) { if(maxValue < array[i]){ maxValue = array[i]; } } return maxValue; }
8.4 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
9.桶排序
9.1 原理
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。
为了使桶排序更加高效,我们需要做到这两点:
- 在额外空间充足的情况下,尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
9.2 算法的步骤
- 设置一个定量的数组当作空桶;
- 遍历输入数据,并且把数据一个一个放到对应的桶里去;
- 对每个不是空的桶进行排序;
- 从不是空的桶里把排好序的数据拼接起来。
9.3 画图解析
9.4 代码实现
public static void bucketSort(int[] arr) { if (arr.length == 0) { return; } int minValue = arr[0]; int maxValue = arr[0]; for (int value : arr) { if (value < minValue) { minValue = value; } else if (value > maxValue) { maxValue = value; } } //得到最大和最小元素 int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的数量 ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketNum); for (int i = 0; i < bucketNum; i++) { bucket.add(new ArrayList<>()); } //将元素放入到桶中 for (int i = 0; i < arr.length; i++) { int num = (arr[i] - minValue) / arr.length; bucket.get(num).add(arr[i]); } for (int i = 0; i < bucket.size(); i++) { //这里是比较,可以选择其他的方式实现,这里为了演示采取Collection的sort Collections.sort(bucket.get(i)); } // 将桶中的元素赋值到原序列 int index = 0; for(int i = 0; i < bucket.size(); i++){ for(int j = 0; j < bucket.get(i).size(); j++){ arr[index++] = bucket.get(i).get(j); } } }
9.5 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n+k) | O(n^2) | O(n+k) | O(n+k) | 稳定 |
10.基数排序
10.1 算法的步骤
- 取得数组中的最大数,并取得位数;
- arr为原始数组,从最低位开始取每个位组成radix数组;
- 对radix进行计数排序(利用计数排序适用于小范围数的特点)
10.2 动图演示
10.3 代码实现
public static int getNumLength(int num){ if(num == 0) return 1; int count = 0; for (int i = num; i != 0; i /= 10) { count++; } return count; } public static void RadixSort(int[] array){ int maxValue = array[0]; for (int i = 0; i < array.length; i++) { if(maxValue < array[i]){ maxValue = array[i]; } } int maxDigit = getNumLength(maxValue); int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { int[][] counter = new int[mod * 2][0]; for (int j = 0; j < array.length; j++) { int bucket = ((array[j] % mod) / dev) + mod; counter[bucket] = arrayAppend(counter[bucket], array[j]); } int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { array[pos++] = value; } } } } public static int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; }
10.4 性能分析
时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n*k) | O(n*2) | O(n*k) | O(n+k) | 稳定 |
总结:
加载全部内容