开始时有序表中只包含一个元素,希尔排序

 基础     |      2020-03-18 13:08

排序原理:

如果引用此文请提供原文出处。

/**

插入排序法 所谓插入排序法乃是将一个数目插入该占据的位置。

前言

 * 功能:插入排序法

假设我们输入的是 “5,1,4,2,3” 我们从第二个数字开始,这个数字是1,我们的任务只要看看1有没有正确的位置,我们的做法是和这个数字左边的数字来比,因此我们比较1和5,1比5小,所以我们就交换1和5,原来的排列就变成了“1,5,4,2,3 ”

排序算法可分类为:插入,选择,交换,归并,基数排序。

 * 基本思想:把n个待排序的元素看成一个有序和无序表,开始时有序表中只包含一个元素,

接下来,我们看第3个数字有没有在正确的位置。这个数字是4,它的左边数字是5,4比5小,所以我们将4和5交换,排列变成了 “1,4,5,2,3 "我们必须继续看4有没有在正确的位置,4的左边是1,1比4小,4就维持不动了。

1、插入排序:直接插入排序,希尔排序。

 * 无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码

再来看第四个数字,这个数字是2,我们将2和它左边的数字相比,都比2大,所以就将2一路往左移动,一直移到2的左边是1,这时候排序变成了 “1,2,4,5,3 ”

2、选择排序:简单选择排序,堆排序。

 * 依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有

最后,我们检查第五个数字,这个数字是3,3必须往左移,一直移到3的左边是2为止,所以我们的排列就变成了 “1,2,3,4,5 ”排序因此完成了。

竞博jbo电竞官网网址下载 ,3、交换排序:冒泡排序,快速排序。

 * 序表。

所谓插入排序法,就是检查第i个数字,如果在它的左边的数字比它大,进行交换,这个动作一直继续下去,直到这个数字的左边数字比它还要小,就可以停止了。插入排序法主要的回圈有两个变数:i和j,每一次执行这个回圈,就会将第i个数字放到左边恰当的位置去。

4、归并排序。

 * 作者:徐守威

跟玩扑克牌的原理类似,每次拿到下一张牌将其插入到正确的位置。

5、基数排序。

 */

代码:

插入排序

插入排序的基本思想是在遍历数组的过程中,假设在序号 i (i>=1)之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,一般情况下,插入排序的时间复杂度和空间复杂度分别为O(n2) 和 O(1)。

通俗说法:从数组第2项数据(即下标index = 1)开始,比较数组左边的数据(即 index < 1 的数据),将数据按顺序插入;移动游标(即 index++ ),依次把数组右边那些没排序的数据插入到左边已经按顺序排列的数组中。

public static int[] InsertSort(int[] array) {

    for(int i =1;i

    int temp = array[i];

    int j = i-1;

    while(j>=0 && temp < array[j] ) {

    array[j+1] = array[j];

    j--;

    }

    array[j+1] = temp;

    }

    return array;

}

package com.xushouwei;

package Sort;

希尔(shell)排序

希尔排序的基本思想是遍历数组的过程中,把数组按下标步长 M 分组,对每组后的数组采用插入算法排序;步长 M 依次递减(即 M-- ),重复执行上述规则,分组的数据有序排列,直到步长为 1 时,数组恰被分成一组,算法结束。

public class ShellSort {

    public static void main(String []args){

    int []arr ={1,4,2,7,9,8,3,6};

    sort(arr);

    System.out.println(Arrays.toString(arr));

    int []arr1 ={1,4,2,7,9,8,3,6};

    sort1(arr1);

    System.out.println(Arrays.toString(arr1));

    }

    /**

      * 希尔排序 针对有序序列在插入时采用交换法

      * @param arr

      */

    public static void sort(int []arr){

    //增量gap,并逐步缩小增量

    for(int gap=arr.length/2;gap>0;gap/=2){

    //从第gap个元素,逐个对其所在组进行直接插入排序操作

    for(int i=gap;i

    int j = i;

    while(j-gap>=0 && arr[j]

    //插入排序采用交换法

    swap(arr,j,j-gap);

    j-=gap;

    }

    }

    }

    }

    /**

      * 希尔排序 针对有序序列在插入时采用移动法。

      * @param arr

      */

    public static void sort1(int []arr){

    //增量gap,并逐步缩小增量

    for(int gap=arr.length/2;gap>0;gap/=2){

    //从第gap个元素,逐个对其所在组进行直接插入排序操作

    for(int i=gap;i

    int j = i;

    int temp = arr[j];

    if(arr[j]

    while(j-gap>=0 && temp

    //移动法

    arr[j] = arr[j-gap];

    j-=gap;

    }

    arr[j] = temp;

    }

    }

    }

    }

    /**

      * 交换数组元素

      * @param arr

      * @param a

      * @param b

      */

    public static void swap(int []arr,int a,int b) {

       arr[a] = arr[a]+arr[b];

       arr[b] = arr[a]-arr[b];

       arr[a] = arr[a]-arr[b];

    }

}

public class T6
{

import java.util.Scanner;

选择排序

选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i+1,…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值/最小值的子流程,所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为O(n2)和O(1)。

通俗说法:从数组第1项(即下标index = 0)开始,比较数组右边的数据(即 index > 0 的数据),找出数组右边中最小的数据与当前数据项进行位置交换;移动游标(即 index++ ),依次找出数组右边最小的数据进行位置交换。 第一次选出来的就是数组中最小数据,第二次选出来的就是数组中第二小数据,依次……。

public int[] sortSelect(int[] arr){

    for (int i = 0; i < arr.length-1; i++) {

    int miniPost = i;

    for (int m = i + 1; m < arr.length; m++) {

    if (arr[m] < arr[miniPost]){

 miniPost = m;

}

}

    if (arr[i] > arr[miniPost]) {

    int temp = arr[i];

    arr[i] = arr[miniPost];

    arr[miniPost] = temp;

    }

    }

    return arr;

}

   /**

public class InsertSort {

堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

堆排序的基本思想是:将数组构造成一个大顶堆,此时,整个数组的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序数组。

通俗说法:将数组安顺序依次构成一颗二叉树,然后从树高 H 的一颗非叶子节点的子树开始,如果左右叶子节点大于父节点则替换,依次从下至上,从右至左调整二叉树结构;当最大数据为根节点时,则根节点与最后节点数据交换,置换后的根节点继续按照大顶堆的规则放入到合适的位置。树高依次递减(即 H -- ),重复执行上述规则,直到树高H为 0 。

public class HeapSort {

    public static void main(String []args){

    int []arr = {9,8,7,6,5,4,3,2,1};

    sort(arr);

    System.out.println(Arrays.toString(arr));

    }

    public static void sort(int []arr){

    //1.构建大顶堆

    for(int i=arr.length/2-1;i>=0;i--){

    //从第一个非叶子结点从下至上,从右至左调整结构

    adjustHeap(arr,i,arr.length);

    }

    //2.调整堆结构+交换堆顶元素与末尾元素

    for(int j=arr.length-1;j>0;j--){

    swap(arr,0,j);//将堆顶元素与末尾元素进行交换

    adjustHeap(arr,0,j);//重新对堆进行调整

    }

    }

    /**

    * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)

    * @param arr

    * @param i

    * @param length

    */

    public static void adjustHeap(int []arr,int i,int length){

    int temp = arr[i];//先取出当前元素i

//从i结点的左子结点开始,也就是2i+1处开始

    for(int k=i*2+1;k

//如果左子结点小于右子结点,k指向右子结点

    if(k+1

    k++;

    }

//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)

    if(arr[k] >temp){

    arr[i] = arr[k];

    i = k;

    }

    }

    arr[i] = temp;//将temp值放到最终的位置

    }

    /**

    * 交换元素

    * @param arr

    * @param a

    * @param b

    */

    public static void swap(int []arr,int a ,int b){

    int temp=arr[a];

    arr[a] = arr[b];

    arr[b] = temp;

    }

}

    * @param args

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
//输入
int[] arr=new int[n];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
//排序
for(int i=1;i<arr.length;i++) {//从第2个元素开始遍历
for(int j=i;j>0;j--) {
if(arr[j]<arr[j-1]) {//如果这个元素比前一个元素小就交换位置,否则就证明该元素之前已经有序就break
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
else {
开始时有序表中只包含一个元素,希尔排序。break;
}
}
}
//输出
for(int i=0;i<arr.length;i++) {
//判断是否为最后一个元素
if(i==arr.length-1) {
System.out.print(arr[i]); //最后一个元素,不用加空格
}else {
System.out.print(arr[i]+" ");
}

冒泡排序

冒泡排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i+1,…n-1] 中,从数组末尾开始比较相邻两个数据的大小,大的数据放在右边,小的数据放在左边,继续相邻数据比较,直到将最小数据放入位置 i 。冒泡排序的时间复杂度和空间复杂度分别是O(n^2)和O(1)。

public int[] sortBubble(int[] array){

  int temp;

   // 第一层循环:表明比较的次数, 比如 length 个元素,

    // 比较次数为 length-1 次(肯定不需和自己比)

  for(int i=0;i

    for (int j = array.length - 1; j > i; j--) {

      if (array[j] < array[j - 1]) {

        temp = array[j];

        array[j] = array[j - 1];

        array[j - 1] = temp;

      }

    }

  }

  return array;

}

    */

}
}

快速排序

快速排序的基本思想是遍历数组的过程中,以数组头数据(即 index=0 的数据)为基数,则需要在剩余的 [i+1,…n-1] 中,从数组末尾开始向左移动,找出比基数小的数据下标 j,然后从第2项数据(即index = 1)开始向右移动,找出比基数大的数据下标 i,交换下标 i 和 j 的数据;继续,直到下标 j 与下标 i 相遇,相遇点下标为 m,然后将基数与相遇点 m 的数据进行交换。此时,相遇点 m 左边数组的数据皆小于基数,右边数组的数据皆大于基数,重复以上步骤,直到相邻数据比较结束。

public static int Partition(int[] a,int p,int r){ 

  int x=a[r-1]; 

  int i=p-1; 

  int temp; 

  for(int j=p;j<=r-1;j++){ 

    if(a[j-1]<=x){ 

      // 交换(a[j-1],a[i-1]); 

      i++; 

      temp=a[j-1]; 

      a[j-1]=a[i-1]; 

      a[i-1]=temp; 

    } 

  } 

  //交换(a[r-1,a[i+1-1]); 

  temp=a[r-1]; 

  a[r-1]=a[i+1-1]; 

  a[i+1-1]=temp; 

  return i+1; 

public static void QuickSort(int[] a,int p,int r){ 

  if(p

    int q=Partition(a,p,r); 

    QuickSort(a,p,q-1); 

    QuickSort(a,q+1,r); 

  } 

//main方法中将数组传入排序方法中处理,之后打印新的数组 

public static void main(String[] stra){ 

  int[] a={7,10,3,5,4,6,2,8,1,9}; 

  QuickSort(a,1,10); 

  for (int i=0;i

  System.out.println(a[i]); 

}

快速排序为什么一定要先从数组末尾向右移动 ?

假如有如下排序数组: 6 1 2 7 9 ,以 6 为基数,如果从数组第 2 项向左边开始移动,找出比基数大的数据为 7 ,然后再从数组末尾向右移动,找出比基数小的数据也为 7,即下标 i 与下标 j 相遇,交换基数 6 和数据 7 的位置。 交换后,此时数据在排序为: 7 1 2 6 9 ,按照快速排序的定义,显然是没有达到预期,基数左边的数据并不是都比基数小(即 7 > 6 )。 换而言之,快速排序如果先从数组末尾向右移动,当相遇点数据大于基数,则不能保证排序的稳定性。

参考文献:

《三个简单、基本的排序算法---插入排序、选择排序、冒泡排序》 https://www.cnblogs.com/Kevin-mao/p/6013452.html

《图解排序算法(二)之希尔排序》 http://www.cnblogs.com/chengxiao/p/6104371.html

《图解排序算法(三)之堆排序》 https://www.cnblogs.com/chengxiao/p/6129630.html

《坐在马桶上看算法:快速排序》 https://blog.csdn.net/vayne_xiao/article/details/53508973

联系方式:

https://github.com/longtian2

如有用请不吝打赏

竞博jbo电竞官网网址下载 1

   public static void main(String[] args) {

}

      // TODO Auto-generated
method stub

      //定义需要排序的数组

      int arr1[]={1,6,0,-1,9,-100,90,10,15,-10};

      //开始排序,创建一个Select类

      InsertSort insertsort=new InsertSort();

      //调用方法开始排序

      insertsort.sort(arr1);

      //输出最后结果

      for(int i=0;i<arr1.length;i++)

      {

        System.out.print(arr1[i]+"
");

      }

   }

}

//定义一个InsertSort类

class InsertSort

{

   //插入排序法

   public void sort(int arr[])

   {

      for(int i=1;i<arr.length;i++)

      {

        //定义一个准备被插入的数

        int insertVal=arr[i];

        //定义插入的位置,即要准备和前一个数比较

        int index=i-1;

         //判断如果插入的位置>=0并且被插入的数<arr[index]

        while(index>=0&&insertVal<arr[index])

        {

           //将把arr[index]向后移动一位

           arr[index+1]=arr[index];

           //让index向前移动一位

           index--;

        }

        //将insertVal插入到适当位置

        arr[index+1]=insertVal;

      }

   }

}