基本排序算法

ゝ一世哀愁。 2022-01-30 15:09 182阅读 0赞

### 算法 ###

*  直接插入排序
 *   *  核心思想
     *  代码示例
 *  希尔排序
 *   *  核心思想
     *  代码示例
 *  堆排序
 *   *  核心思想
     *  代码示例
 *  快速排序
 *   *  核心思想
     *  代码示例
 *  归并排序
 *   *  核心思想
     *  代码示例

# 直接插入排序 #

## 核心思想 ##

每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。  
![直接插入][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70]

## 代码示例 ##

public class InsertSort{ 
        public static void main(String [] args){ 
            int[] a=[49,38,65,97,76,13,27,49,78,34,12,64,1];
            System.out.println("排序之前：");
            for(int i=0; i<a.length; i++){ 
                System.out.print(a[i]+" ");
            }
            //排序
            for(int i=1; i<a.length; i++){ 
                //待插入元素
                int temp=a[i];
                int j;
    
                for(j=i-1; j>=0; j--){ 
                    //将大于temp的往后移动一位
                    if(a[j]>temp){ 
                        a[j+1]=a[j];
                    }else{ 
                        break;
                    }
                }
                //插进来
                a[j+1]=temp;
            }
    
            System.out.println();
            System.out.print("排序之后: ");
            for(int i=0; i<a.length; i++){ 
                System.out.print(a[i]+" ");
            }
        }
    }

# 希尔排序 #

## 核心思想 ##

把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。  
![希尔排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 1]

## 代码示例 ##

public class HeerSort{ 
        public static void main(String [] args){ 
            int[] a =[49,38,65,97,76,13,27,49,78,34,12,64,1,33,85,29];
            System.out.println("排序之前： ");
            for(int i=0; i<a.length; i++){ 
                System.out.print(a[i]+" ");
            }
            System.out.println();
            //定义一个增量
            int d=a.length/2;
            while(true){ 
                //分为几个组
                for(int i=0; i<d; i++){ 
                    //比较交换
                    for(int j=i; j+d<a.length; j+=d){ 
                        int temp;
                        //交换
                        if(a[j]>a[j+d]){ 
                            temp=a[j];
                            a[j]=a[j+d];
                            a[j+d]=temp;
                        }
                    }
                }
                if(d==1){ break;}
                //缩小增量
                d--;
            }
            
            System.out.println();
            System.out.print("排序之后: ");
            for(int i=0; i<a.length; i++){ 
                System.out.print(a[i]+" ");
            }
        }
    }

# 堆排序 #

## 核心思想 ##

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了  
![堆排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 2]  
**步骤一** 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)

1）假定给定无序序列结构如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 3]  
2）此时我们从最后一个非叶子节点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 4]  
3）找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 5]  
这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 6]  
此时，我们就将一个无序序列构造成了一个大顶堆

**步骤二** 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换

1)将堆顶元素9和末尾元素4进行交换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 7]  
2)重新调整结构，使其继续满足堆定义  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 8]  
3)再将堆顶元素8与末尾元素5进行交换，得到第二大元素8  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 9]  
4)后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 10]  
**基本思路**  
1、将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆  
2、将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端  
3、重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

## 代码示例 ##

public class HeapSort{ 
        public static void main(String [] args){ 
            HeapSort heapSort = new HeapSort();
            int[] array={ 19,8,27,6,35,14,3,12,1,0,9,10,7};
            
            //排序之前打印数组
            System.out.println("Before heap:");
            heapSort.printArray(array);
            
            heapSort.heapSort(array);
            
            //排序之后打印数组
            System.out.println("After heap sort:");
            heapSort.printArray(array);
        }
        
        //构建最大堆
        public void heapSort(int[] array){ 
            if(array==null || array.length<=1){ 
               return; 
            }
            
            //创建大堆
            buildMaxHeap(array);
            
            for (int i = array.length - 1; i >= 1; i--) { 
                //最大的在0位置，那么开始沉降，这样每交换一次最大的值就丢到最后了
                exchangeElements(array, 0, i);
                //继续获取0位置最大值
                maxHeap(array, i, 0);
            }
        }
        
        //创建大堆
        private void buildMaxHeap(int[] array){ 
            if (array == null || array.length <= 1) { 
                return;
            }
            int half = (array.length-1) / 2;
            for (int i = half; i >= 0; i--) { 
                //构造最大堆
                maxHeap(array, array.length, i);
            }
        }
        
        /** * 构造大堆的数组 * @param array 构造最大堆的数组 * @param heapSize 构造的数组长度元素数量 * @param index 当前位置 */
        private void maxHeap(int[] array,int heapSize, int index){ 
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int largest = index;
            if (left < heapSize && array[left] > array[index]) { 
                largest = left;
            }
            if (right < heapSize && array[right] > array[largest]) { 
                largest = right;
            }
            if (index != largest) { 
                //数据交换
                exchangeElements(array, index, largest);
                //构造大堆
                maxHeap(array, heapSize, largest);
            }
        }
        
        //在数组array中进行两个下标元素交换
        public void exchangeElements(int[] array, int i int largest) {   
            int temp = array[i];  
            array[i] = array[largest];  
            array[largest] = temp;  
        }
        
        //打印数组
        public void printArray(int[] array) {   
            System.out.print("{");  
            for (int i = 0; i < array.length; i++) {   
                System.out.print(array[i]);  
                if (i < array.length - 1) {   
                    System.out.print(", ");  
                }  
            }  
            System.out.println("}");
        }
        
    }

# 快速排序 #

## 核心思想 ##

**1、三数取中**  
在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 11]  
**2、根据枢纽值进行分割**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 12]

## 代码示例 ##

public class QuickSort{ 
        public static void main(String [] args){ 
            QuickSort quickSort = new QuickSort();
            int [] a = { 19,2,3,90,67,33,-7,24,3,56,34,5};
            
            quickSort.quick(a);
            for(int num :a){ 
                System.out.println(" "+num);
            }
        }
        
        //排序
        public void quick(int[] a){ 
            if(a.length>0){ 
                quickSort(a,0,a.length-1);
            }
        }
        
        //快速排序
        private void quickSort(int[] a, int low,int high){ 
            if(low<high){ 
                //
                int middle = getMiddle(a,low,high);
                
                quickSort(a,0,middle-1);
                
                quickSort(a,middle+1,high);
            }
        }
        
        //获取中间下标
        private int getMiddle(int[] a,int low,int high){ 
            //基准元素
            int tmp = a[low];
            
            while(low<high){ 
                while(low<high && a[high]>=temp){ 
                    high--;
                }
                a[low] = a[high];
                
                while(low<high && a[low]<=temp){ 
                    low++;
                }
                a[high] = a[low];
            }
            
            //插入到排序后正确的位置
            a[low] = temp;
            return low;
        }
    }

# 归并排序 #

## 核心思想 ##

利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 16]

## 代码示例 ##

public class MergeSort{ 
        public void main(String [] args){ 
            MergeSort mergeSort = new MergeSort();
        int [] a = new int[]{ 90,3,2,67,44,-9,87,65,11,9,2,8};
        mergeSort.mergeSort(a, 0, a.length-1);
        for(int n:a){ 
          System.out.print(" "+n);
        }
        }
        
        //排序
        public void mergeSort(int[] a,int left,int right){ 
        if(left<right){ 
                //获取中间值
          int middle = (left+right)/2;
                
          mergeSort(a, left, middle);
                
          mergeSort(a,middle+1,right);
                
          merge(a,left,middle,right);//合并
        }
      }
        
        //合并
        private void merge(int[] a, int left, int middle, int right) { 
        int [] tmpArray = new int[a.length];
        int rightStart = middle+1;
        int tmp = left;
        int third = left;
        //比较两个小数组相应下标位置的数组大小，小的先放进新数组
        while(left<=middle&&rightStart<=right){ 
          if(a[left]<=a[rightStart]){ 
            tmpArray[third++] = a [left++];
          }else{ 
            tmpArray[third++] = a[rightStart++];
          }
        }
        //如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组
        while(left<=middle){ 
          tmpArray[third++] = a[left++];
        }
        //如果右边还有数据......
        while(rightStart<=right){ 
          tmpArray[third++] = a[rightStart++];
        }
        while(tmp<=right){ 
          a[tmp] = tmpArray[tmp++];
        }
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70]: /images/20220130/66b1f58271c14ae081836a8586797a65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 1]: /images/20220130/b45d278a1df74578b21f624be57917bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 2]: /images/20220130/e1cba4e821f84a679d2413c32e7456a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 3]: /images/20220130/fd9bad24929046f4bdc41c7468687f76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 4]: /images/20220130/def0d0c0ea5a4a94aabe83619aecec64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 5]: /images/20220130/5cb2df12e3ce40f7ab519e72e2fd4425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 6]: /images/20220130/d25b18a2d29d45e3a0fac9992ce93766.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 7]: /images/20220130/408ed9a0b5244443b5f4f428b4c624f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 8]: /images/20220130/7899da6c00dc4026b00fb51801bfe4c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 9]: /images/20220130/a50beec880bd4d2681f5fb9c8b2d4521.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 10]: /images/20220130/97c965f513ae4fbe8b6f3757697a8030.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 11]: /images/20220130/eb526fad1b574709a51bb44eae681820.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 12]: /images/20220130/04cb286e6ffd40c0aee6447ca955dde6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 13]: /images/20220130/fa1c9862df3b4254b0ebd1a9d80f7a8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 14]: /images/20220130/a3793430ab184c31976c22aa1bdb3ae8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 15]: /images/20220130/040dc0637530471ca09faca912d8c554.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXppdGVuZzAyMjg_size_16_color_FFFFFF_t_70 16]: /images/20220130/c0c1527ec4d74ac69f8b8beb3ffab05a.png