目录
注意:本文所有排序默认升序
思路:
代码如下:
- public void insertSort(int[] array){
- for(int i = 1; i < array.length; i++){
- int key = array[i];
- int j = i - 1;
- for(; j >= 0; j--){
- if(array[j] > key){
- array[j + 1] = array[j];
- }else{
- break;
- }
- }
- array[j + 1] = key;
- }
- }
分析:
思路:
代码如下:
- public void shell3(int[] array, int gap){
- for(int i = gap ; i < array.length; i++){
- int key = array[i];
- int j = i - gap;
- for(; j >= 0; j -= gap){
- if(array[j] > key){
- array[j + gap] = array[j];
- }else{
- break;
- }
- }
- array[j + gap] = key;
- }
- }
- public void shellSort3(int[] array){
- int gap = array.length;
- while(gap > 1){
- gap /= 2;
- shell3(array, gap);
- }
- shell3(array, 1);
- }
分析:
思路:
代码如下:
- public void chooseSort(int[] array){
- for(int i = 0; i < array.length; i++){
- for(int j = i + 1; j < array.length; j++){
- if(array[i] > array[j]){
- int tmp = array[i];
- array[i] = array[j];
- array[j] = tmp;
- }
- }
- }
- }
分析:
思路:
代码如下:
- public void bubbleSort(int[] array){
- for(int i = 0; i < array.length - 1; i++){
- for(int j = 0; j < array.length - i - 1; j++){
- if(array[j] > array[j + 1]){
- int tmp = array[j];
- array[j] = array[j + 1];
- array[j + 1] = tmp;
- }
- }
- }
- }
- 对于冒泡排序,若已排好序,在这样排,实在浪费时间
- 可以建立一个flag判断,是否有进行排序操作,优化如下:
- public void bubbleSort(int[] array){
- for(int i = 0; i < array.length - 1; i++){
- boolean flag = false;
- for(int j = 0; j < array.length - i - 1; j++){
- if(array[j] > array[j + 1]){
- int tmp = array[j];
- array[j] = array[j + 1];
- array[j + 1] = tmp;
- flag = true;
- }
- }
- if(!flag){
- break;
- }
- }
- }
分析:
思路:
代码如下:
- //堆排序
- public void heapSort(int[] array){
- createBigHeap(array);
- int end = array.length - 1;
- while(end > 0){
- //这里不需要在判断大小,因为大根堆最上面本来就是最大的,直接交换即可
- swap(array, end, 0);
- adjustmentDown(array, 0, end);
- end--;
- }
- }
- //创建大根堆
- public void createBigHeap(int[] array){
- int len = array.length;
- for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--){
- adjustmentDown(array, parent, len);
- }
- }
- //向下调整
- public void adjustmentDown(int[] array, int parent, int len){
- int child = parent * 2 + 1;
- while(child < len){
- //必须保证要有右孩子
- if(child + 1 < len && array[child] < array[child + 1]){
- child++;
- }
- if(array[parent] < array[child]){
- swap(array, parent, child);
- parent = child;
- child = parent * 2 + 1;
- }
- else{
- //如果根节点大于孩子结点后面就没必要比较了
- break;
- }
- }
- }
- //交换
- public void swap(int[] array, int i, int j){
- int tmp = array[i];
- array[i] = array[j];
- array[j] = tmp;
- }
分析:
思路:(递归思路)
如下代码:(递归,未优化)
- //快速排序
- //找基准
- public int fundPivot(int[] array,int start, int end){
- int key = array[start];
- while(start < end){
- //取等于号方式头尾元素相等造成死循环
- //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
- //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
- while(start < end && key <= array[end]){
- end--;
- }
- array[start] = array[end];
- while(start < end && array[start] <= key){
- start++;
- }
- array[end] = array[start];
- }
- //将基准放入停止时的位置
- array[start] = key;
- return start;
- }
- //分组递归
- public void quick(int[] array, int left, int right){
- if(left >= right){
- return;
- }
- int pivot = fundPivot(array, left, right);
- quick(array, left, pivot - 1);
- quick(array, pivot + 1, right);
- }
- //充当个接口,同一传入的值为数组
- public void quickSort(int[] array){
- quick(array, 0, array.length - 1);
- }
存在的问题:当给的数据是有序(升序或降序)的,这时的快排时间复杂度会达到O(N^2),仅在元素集合是杂乱无章的情况下时间复杂度接近O(N*logN)为了解决这个问题,引入了三数取中法;
三数取中法思路:对待排序元素给定三个下标,第一个下标left指向最左边的元素,第二个下标right指向最右边的元素,第三个下标mid指向指向中间值-> (left + right) / 2,得到这三个下标后再求出这三个下标所指向的数据的中位数作为“基准”,这样找出的基准更可以将元素集合均分(基本就是二分),在数据有序情况下大大降低时间复杂度,趋近O(N*logN)。
如下代码:(第一步优化)
- //快速排序
- //找基准
- public int fundPivot(int[] array,int start, int end){
- int key = array[start];
- while(start < end){
- //取等于号方式头尾元素相等造成死循环
- //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
- //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
- while(start < end && key <= array[end]){
- end--;
- }
- array[start] = array[end];
- while(start < end && array[start] <= key){
- start++;
- }
- array[end] = array[start];
- }
- //将基准放入停止时的位置
- array[start] = key;
- return start;
- }
- //寻找中间值交换
- public int funMidIndex(int[] array, int left, int right){
- int mid = (left + right) / 2;
- if(array[left] < array[right]){
- if(array[mid] < array[left]){
- return left;
- }else if(array[right] < array[mid]){
- return right;
- }else{
- return mid;
- }
- }else{
- if(array[left] < array[mid]){
- return left;
- }else if(array[mid] < array[right]){
- return right;
- }else{
- return mid;
- }
- }
- }
- //分组递归
- public void quick(int[] array, int left, int right){
- if(left >= right){
- return;
- }
- int midIndex = funMidIndex(array, left, right);
- swap(array, left, midIndex);
- int pivot = fundPivot(array, left, right);
- quick(array, left, pivot - 1);
- quick(array, pivot + 1, right);
- }
- //充当个接口,同一传入的值为数组
- public void quickSort(int[] array){
- quick(array, 0, array.length - 1);
- }
存在问题:递归的层次太多,元素集合过大可能导致栈溢出;
解决办法:即使三数取中法一定程度上也减少了递归的深度,但是在庞大的数据下不足以支撑,减少递归层次;想象以下,递归最后一层实现了多少次递归呢?是2^(n - 1),而整个快速排序总共才递归2^n - 1,相当于最后一层递归就占了整个快排递归数量的一半多,不难想到,递归到结尾的时候,完全没有必要再递归下去,因为数据已经趋于有序,所以这个时候就可以用到插入排序,大大减少递归次数,防止栈溢出。
代码如下:(递归层次的优化)
- //快速排序
- //插入排序
- public void insertSort(int[] array, int start, int end){
- for(int i = start + 1; i <= end; i++){
- int key = array[i];
- int j = i - 1;
- for(; j >= 0; j--){
- if(array[j] > key){
- array[j + 1] = array[j];
- }else{
- break;
- }
- }
- array[j + 1] = key;
- }
- }
- //找基准
- public int fundPivot(int[] array,int start, int end){
- int key = array[start];
- while(start < end){
- //取等于号方式头尾元素相等造成死循环
- //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
- //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
- while(start < end && key <= array[end]){
- end--;
- }
- array[start] = array[end];
- while(start < end && array[start] <= key){
- start++;
- }
- array[end] = array[start];
- }
- //将基准放入停止时的位置
- array[start] = key;
- return start;
- }
- //寻找中间值交换
- public int funMidIndex(int[] array, int left, int right){
- int mid = (left + right) / 2;
- if(array[left] < array[right]){
- if(array[mid] < array[left]){
- return left;
- }else if(array[right] < array[mid]){
- return right;
- }else{
- return mid;
- }
- }else{
- if(array[left] < array[mid]){
- return left;
- }else if(array[mid] < array[right]){
- return right;
- }else{
- return mid;
- }
- }
- }
- //分组递归
- public void quick(int[] array, int left, int right){
- if(left >= right){
- return;
- }
- //假设数据非常大
- //这里相当于减少了7层递归
- if(right - left + 1 <= 7){
- insertSort(array, left, right);
- }
- int midIndex = funMidIndex(array, left, right);
- swap(array, left, midIndex);
- int pivot = fundPivot(array, left, right);
- quick(array, left, pivot - 1);
- quick(array, pivot + 1, right);
- }
- //充当个接口,同一传入的值为数组
- public void quickSort(int[] array){
- quick(array, 0, array.length - 1);
- }
分析:(最后一次优化)
思路:大致思路与递归相似,很多重复的东西下面就不细讲了(如三数取中法...)
代码如下:(经三数取中法优化)
- //非递归快排
- //寻找中间值交换
- public int funMidIndex(int[] array, int left, int right){
- int mid = (left + right) / 2;
- if(array[left] < array[right]){
- if(array[mid] < array[left]){
- return left;
- }else if(array[right] < array[mid]){
- return right;
- }else{
- return mid;
- }
- }else{
- if(array[left] < array[mid]){
- return left;
- }else if(array[mid] < array[right]){
- return right;
- }else{
- return mid;
- }
- }
- }
- //找基准
- public int fundPivot(int[] array,int start, int end){
- int key = array[start];
- while(start < end){
- //取等于号方式头尾元素相等造成死循环
- //tart < end再次判断是因为,有可能end这边的值都比key大,最后越界访问
- //一定要先从后面end遍历,最后结束位置的时候就把大的放前面了
- while(start < end && key <= array[end]){
- end--;
- }
- array[start] = array[end];
- while(start < end && array[start] <= key){
- start++;
- }
- array[end] = array[start];
- }
- //将基准放入停止时的位置
- array[start] = key;
- return start;
- }
- public void quickSort(int[] array){
- int left = 0;
- int right = array.length - 1;
- Stack
stack = new Stack<>(); - //三数取中法优化
- int midIndex = funMidIndex(array, left, right);
- swap(array, left, midIndex);
- int pivot = fundPivot(array, left, right);
- //若基准左边或右边的数据不超过一个,则将下标压入栈,否则就是有序
- if(left + 1 < pivot){
- stack.push(left);
- stack.push(pivot - 1);
- }
- if(right - 1 > pivot){
- stack.push(pivot + 1);
- stack.push(right);
- }
- //只要栈不为空,就每次弹出栈顶的两个元素作为左右边界,继续进行如上操作
- while(!stack.isEmpty()){
- right = stack.pop();
- left = stack.pop();
- midIndex = funMidIndex(array, left, right);
- swap(array, left, midIndex);
- pivot = fundPivot(array, left, right);
- if(left + 1 < pivot){
- stack.push(left);
- stack.push(pivot - 1);
- }
- if(right - 1 > pivot){
- stack.push(pivot + 1);
- stack.push(right);
- }
- }
-
- }
思路:
代码如下:
- //归并排序
- private void mergeFunc(int[] array, int left, int right){
- if(left == right){
- return;
- }
- int mid = (left + right) / 2;
- //分解左边(包含mid下标元素)
- mergeFunc(array, left, mid);
- //分解右边
- mergeFunc(array, mid + 1, right);
- //合并
- merge(array, left, right, mid);
- }
- //合并
- private void merge(int[] array, int start, int end, int midIndex){
- int[] tmpArr = new int[end - start + 1];
- //tmpArr数组的零下标
- int k = 0;
- int s1 = start;
- int s2 = midIndex + 1;
- //两个同时比较
- while(s1 <= midIndex && s2 <= end){
- //这里因为是<=所以才是一个稳定的排序
- if(array[s1] <= array[s2]){
- tmpArr[k++] = array[s1++];
- }else{
- tmpArr[k++] = array[s2++];
- }
- }
- //若比较完后,还剩余一方未比较完,直接将剩下的一方拼上
- while(s1 <= midIndex){
- tmpArr[k++] = array[s1++];
- }
- while(s2 <= end){
- tmpArr[k++] = array[s2++];
- }
- //把排好序的数字从start处开始拷贝回原数组
- for(int i = 0; i < k; i++){
- array[i + start] = tmpArr[i];
- }
- }
- public void mergeSort(int[] array){
- mergeFunc(array, 0, array.length - 1);
- }
分析:
思路:(一定要注意指针下标的合理性)
1.先将整个数据其分成一个数据为一组,共分为两组,如下图(红为一组,蓝为一组)
2.两组之间相互比较,并排序,如下图
3.再将组距放大一倍,相当于一组两个元素,如下图
4.给定指针如下图(一组一个元素的时候就有指针,当时表示用处不大,此时标注方便理解)
5.接下来就是合并两个有序的数组 :创建一个大小可以容纳所有元素的数组,先比较s1,s2谁小,将小的放入新数组,如下图
6.继续重复以上3~5操作,直到s1 > e1或s2 > e2时停止,若这两组,有一方先停止,就将剩下的一方直接从后加到数组中去 ,再继续扩到组距(直到大于数组总大小为止)...
代码如下:
- //合并
- private void merge(int[] array, int start, int end, int midIndex){
- int[] tmpArr = new int[end - start + 1];
- //tmpArr数组的零下标
- int k = 0;
- int s1 = start;
- int s2 = midIndex + 1;
- //两个同时比较
- while(s1 <= midIndex && s2 <= end){
- //这里因为是<=所以才是一个稳定的排序
- if(array[s1] <= array[s2]){
- tmpArr[k++] = array[s1++];
- }else{
- tmpArr[k++] = array[s2++];
- }
- }
- //若比较完后,还剩余一方未比较完,直接将剩下的一方拼上
- while(s1 <= midIndex){
- tmpArr[k++] = array[s1++];
- }
- while(s2 <= end){
- tmpArr[k++] = array[s2++];
- }
- //把排好序的数字从start处开始拷贝回原数组
- for(int i = 0; i < k; i++){
- array[i + start] = tmpArr[i];
- }
- }
- public void mergeSort(int[] array){
- int gap = 1;
- while(gap < array.length){
- // i+= gap*2 是为了保证s1可以跳过e2、s2、e2到下一个待排序位置
- for(int i = 0; i < array.length; i += gap * 2){
- //首先能进循环i一定合法
- int s1 = i;
- int e1 = i + gap - 1;
- //注意保证指针不会越界!一旦越界采取强制措施,如下
- if(e1 > array.length - 1){
- e1 = array.length - 1;
- }
- int s2 = e1 + 1;
- if(s2 > array.length - 1){
- s2 = array.length - 1;
- }
- int e2 = s2 + gap - 1;
- if(e2 > array.length - 1){
- e2 = array.length - 1;
- }
- merge(array, s1, e2, e1);
- }
- gap *= 2;
- }
- }
分析:
思路:
代码如下:
- public void countSort(int[] array){
- int maxIndex = array[0];
- int minIndex = array[0];
- for(int i = 0; i < array.length; i++){
- if(array[i] > maxIndex){
- maxIndex = array[i];
- }
- if(array[i] < minIndex){
- minIndex = array[i];
- }
- }
- //假设最大值66,最小值60,则有66 - 60 = 6个数据,而60~66实际上有7个数据,所以加一
- int[] countArr = new int[maxIndex - minIndex + 1];
- //开始计数
- for(int i = 0; i < array.length; i++){
- countArr[array[i] - minIndex]++;
- }
- //写入原数组
- int index = 0;//array的下标
- for(int i = 0; i < countArr.length; i++){
- while(countArr[i] != 0){
- array[index] = i + minIndex;
- countArr[i]--;
- index++;
- }
- }
- }
分析: