寄存在数组奥迪Q3中,则将相比成分向后运动以腾出岗位

前言


  本文集将用java语言实现包括插入排序(直接插入、折半插入、希尔排序),调换排序(飞速排序和冒泡排序),选取排序,堆排序,归并排序以及基数排序在内的享有内排序算法。就算都很粗大略且实际开销差不多已使用不到(Arrays.Sort和Collection.Sort可径直调用),但是那些属于八个程序员的底子,熟练通晓是必须的。

前言:

贰零壹陆年九月21号起始读书排序算法及其关键考虑,并经过代码落成

算法


  直接插入排序的构思便是当发现系列不是有序的气象下时,将待排序成分插入到前面已经稳步的队列中。所以怎么插是着力难点,其实说到底照旧找到待排序成分的插入地点。由于是从小到大排序,可由待排序成分的前三个岗位上马从后迈入比较,若发现相比较成分大于待排序成分,则将相比成分向后运动以腾出地点。最后将元素赋值给排序甘休腾出的地方。
  边相比边移位是其性状,所以有待优化的地点。后续的折半插入和希尔排序都是对间接插入排序的一种优化。时间复杂度为o(n*n)。

插入排序

插入排序有二种:

  • 直接插入排序
  • 折半插入排序

例子


以序列 4 3 1 2 5为例

示例

直接插入排序

Codes


package com.fairy.InnerSort;

import java.util.Scanner;

/**
 * 直接插入排序
 * @author Fairy2016
 *
 */
public class DirectInsertSort {

    public static void sort(int a[], int n) {
        int i,j;
        for(i = 2; i <= n; i++) {
            if(a[i-1] > a[i]) {
                a[0] = a[i];//a[0]作为探针,既存储待排序元素又作循环停止标志,省却if判断
                for(j = i-1; a[j] > a[0]; j--) {
                    a[j+1] = a[j];//遇到比a[i]大的向后移位,腾出位置
                }
                a[j+1] = a[0];//将待排序元素赋值到最终位置
            }
        }
    }

    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
    }
}

算法思想:

存在n +
3个记录,存放在数组RAV4中,重新陈设记录在数组中的存放顺序,使得按主要性字有序即LAND[0].key
<= R2.Key <= …<=R[n].key(有序表)

  • 若是待排序的记录存放在数组翼虎[1..n]中。
  • 初始时,R[1]自成叁个有序区,无序区为RAV4[2..n]。
  • 从i=2起直至i=n为止,依次将R[i]插入当前的稳步区Evoque[1..i-1]中,生成含n个记录的有序区。

算法描述

图片 1

直接插入排序演示图

  • (1)若比较r[0] < r[i]时, j = i – 1; //
    从第i个记录前行测试插入地点,用r[0]为帮忙单元
  • (2)若r[0].key >=r[j].key 转(4)
  • (3)若r[0].key < r[j].key时,r[j + 1] = r[j]; j–;转(2)
    // 调整待插入地点
  • (4) r[j + 1] = r[0];结束

算法实现

  #include <stdio.h>
  #define N 10

  void insertSort(int a[],int length) {
    int j;
    for (int i = 1; i <= length; i++) { 
        a[0] = a[i];   // 将第i个待排序记录赋值给a[0],a[0]位置为哨兵
        j = i - 1;  // 此时的j为哨兵的前一个元素
        while (a[0] < a[j] && j >=0) { // 将第i个待排序记录同前面的i - 1 个记录比较,并为第j个记录寻找合适的插入位置
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = a[0]; // 此时的j为合适插入位置

    }   
  }

  void main() {
    int a[N + 1],i;
    for (i = 1;i <= N; i++) {
        scanf("%d",&a[i]);
    }
    insertSort(&a,N);
    printf("Input Sort:\n");
    for (i = 1; i < N + 1; i++)  {
        printf("%d",a[i]);
    }
}

算法分析

时刻复杂度 O(n2)

  • 向有序表(昂Cora1[0].key <= R[1].key <= … R[j –
    1].key)中各个插入记录的操作,实行了n –
    1趟,每次操作分为相比较根本字和活动记录,而正如的次数和移动的次数取决于待排体系按主要性字的起初排列。
  • 最好状态:待排种类已按重要性字正序,相比次数Cmin = n – 一回,移动次数Mmin = 0 次
  • 最坏情况:待排种类已按主要性字逆序
![](https://upload-images.jianshu.io/upload_images/1231308-40ade90dabea1fff.png)

最坏情况比较和移动次数.png
  • 平均景况:待排序恐怕现身的种种排列的可能率一样
![](https://upload-images.jianshu.io/upload_images/1231308-9aadbf867ab13b23.png)

平均情况比较和移动次数.png
  • 间接插入算法的安定团结:是平稳的排序方法。

空间复杂度

  • 亟待二个推抢控件(监视哨),接济空间复杂度S(n)=O(1),此算法是就地排序

折半插入排序

直接插入排序算法渐变,且便于达成。当排序的数据n相当的小时,这是一种很好的排序方法。可是,常常待排序类别中的记录数据n一点都不小,则不宜使用直接插入排序。折半插入排序(binary
insertion
sort)是对插入排序算法的一种立异,由于排序算法过程中,正是无休止的逐条将成分插入后边已排好序的行列中。由于前半片段为已排好序的数列,那样大家不用按顺序依次寻找插入点,能够利用折半查找的法门来加速寻找插入点的速度。

算法思想:

折半插入排序

  • 向有序表中插入一个记录,插入地方是通过对有序表中著录按首要性字各个相比较获得的
  • 平均情形下总比较次数n2/4
  • 经过二分有序表来明确插入地方,既一回相比较,通过待插入记录与平稳表居中的记录按主要性字相比,将有类别一份为二,下次可比在其间叁个静止子表中开始展览,将字表又一分为二。那样继续下去,直到要相比较字表中唯有3个笔录时,相比三次就规定了插入位置

算法流程图

图片 2

折半插入排序流程图

算法完结

算法分析

日子复杂度 O(n2)

折半插入排序算法是一种祥和的排序算法,比直接插入算法分明收缩了首要字以内相比的次数,因而进程比直接插入排序算法快,但记录移动的次数没有变,所以折半插入排序算法的时光复杂度照旧为O(n^2),与直接插入排序算法相同。附加空间O(1)。

  • 祥和:是政通人和排序

空间复杂度

  • 亟需多少个支持控件,附加空间O(1)。,此算法是就地排序

Hill排序

希尔排序(Shell
Sort)是插入排序的一种。也称减少增量排序,是直接插入排序算法的一种更敏捷的改进版本。希尔排序是非稳定排序算法。

算法思想:

希尔排序

  • 选料1个肥瘦系列t(1),t(2),…,t(<sub >k),其中t(i) >
    t(j), t(k) = 1。
  • 按上涨幅度连串个数k,对队列实行k趟排序
  • 每一次排序依照对应的步长t(i),将待排系列分隔成几何长度为m的子类别,分别对各子表进行直接插入排序。仅步长因子为1时,整个系列作为1个表来处理,表长度即为整个体系的长度。

算法流程图

图片 3

希尔排序流程图

p:步长因子
颜色相同:每一回排序依照对应的步长p,将待排类别分隔成几何长度为m的子体系,分别对各子表进行直接插入排序。仅步长因子为1时,整个类别作为八个表来处理,表长度即为整个种类的长度。

算法达成

    #include<stdio.h>
    #include<math.h>

    #define MAXNUM 10

    void main()
    {
        void shellSort(int array[],int n,int t);//t为排序趟数
        int array[MAXNUM],i;
        for(i=0;i<MAXNUM;i++)
            scanf("%d",&array[i]);
        shellSort(array,MAXNUM,int(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分
        for(i=0;i<MAXNUM;i++)
            printf("%d ",array[i]);
        printf("\n");
    }

    //根据当前增量进行插入排序
    void shellInsert(int array[],int n,int dk)
    {
        int i,j,temp;
        for(i=dk;i<n;i++)//分别向每组的有序区域插入
        {
            temp=array[i];
            for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
                array[j+dk]=array[j];
            if(j!=i-dk)
                array[j+dk]=temp;//插入
        }
    }

    //计算Hibbard增量
    int dkHibbard(int t,int k)
    {
        return int(pow(2,t-k+1)-1);
    }

    //希尔排序
    void shellSort(int array[],int n,int t)
    {
        void shellInsert(int array[],int n,int dk);
        int i;
        for(i=1;i<=t;i++)
            shellInsert(array,n,dkHibbard(t,i));
    }

或:
#include <stdio.h>

#define MAXNUM 10

void shellSort(int a[],int n) {

int i,j,gap,x;
gap = n / 2; // 初始步长一般为待排序文件长度的一半
while (gap > 0) {   // 当步长大于0时继续排序

    for ( i = gap; i < n; i++) {
        // 从每个子序列的第一个位置开始比较
        j = i - gap;   // 
        while (j >= 0) 
            if (a[j] > a[j + gap]) { // (1) a[j]前面的元素,(2) a[j + gap]后面的元素,如果(1) > (2) 交换两个元素的位置

                x = a[j];
                a[j] = a[j + gap];
                a[j + gap] = x;
                j = j - gap;  // 无符号,当前子序列的下一个结点
                printf("j--!%d",j);
            } else j = -1;  
    }
    gap =  gap / 2; // 步长减半

}
}

void main() {
int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

shellSort(a,MAXNUM);

for (int i = 0; i < MAXNUM; i++) {

    printf("%d ",a[i]);
}
}

算法分析

时间复杂度 O(n2)

希尔排序是根据分化幅度对成分实行,当刚初始成分很无序的时候,步长最大,所以插入排序的要素个数很少,速度相当的慢;当成分基本有序了,步长相当的小,插入排序对于有序的队列作用很高。所以,希尔排序的时间复杂度]会比o(n^2)好一些。

  • 平安:是安静排序

空间复杂度

  • 须要贰个帮忙控件,附加空间O(1)。,此算法是就地排序

冒泡排序

冒泡排序:

  • 冒泡排序
  • 优化冒泡排序

算法思想:

  • j = length – 1(j为数组最后二个因素)
  • 若i >= j ,一趟冒泡甘休
  • 若a[j] < a[j – 1] 交换
  • i++下一趟

算法流程图

图片 4

冒泡排序流程图

算法达成

#include <stdio.h>

#define MAXNUM 10

void bubbleSort(int a[],int length) {

    for (int i = 0; i < length - 1; ++i)  
        // 趟数,最后一趟已排序
        for (int j = length - 1;j > i;--j) {
            // 如果前一个元素大于后一个元素则交换
            if (a[j] < a[j - 1]) {
                a[j] = a[j] ^ a[j - 1];
                a[j - 1] = a[j] ^ a[j - 1];
                a[j] = a[j] ^ a[j - 1];
            }

        }

}

void main() {

    int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

    bubbleSort(a,sizeof(a) / sizeof(int));

    for (int i = 0; i < MAXNUM ; i++) {
        printf("%d ",a[i]);
    }
}

优化冒泡排序代码:

    #include <stdio.h>

    #define MAXNUM 10

    void bubbleSort(int a[],int length) {
        int recordSwapValue;
        int swapValue = 0;
        for (int i = 0; i < length - 1;i++) {
            recordSwapValue = swapValue;  //i... recordSwapValue的索引为有序
            for (int j = length - 1; j > recordSwapValue; j--) { // R[i...recordSwapValue]或R[0...recordSwapValue]区间有序的,遍历区间由R[i...length] 缩减到[recordSwapValue..length]。
                if (a[i] > a[i - 1]) {
                    a[j] = a[j] ^ a[j - 1];
                    a[j - 1] = a[j] ^ a[j - 1];
                    a[j] = a[j] ^ a[j - 1];
                    swapValue = j; // 记录交换位置的索引值
                }
            }
            // 如果值相当,整个过程
            if (recordSwapValue == swapValue) {
                break;
            }

        }
    }

    void main() {

        int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};

        bubbleSort(a,sizeof(a) / sizeof(int));

        for (int i = 0; i < MAXNUM ; i++) {
            printf("%d ",a[i]);
        }
    }

算法分析

岁月复杂度 O(n2)

  • 向有序表(R1[0].key <= R[1].key <= … R[j –
    1].key)中每一个插入记录的操作,实行了n –
    1趟,每一趟操作分为比较重庆大学字和移动记录,而正如的次数和平运动动的次数取决于待排系列按重要性字的起来排列。
  • 最好状态:待排类别已按主要性字正序,相比较次数Cmin = n – 一回,移动次数Mmin = 0 次
  • 最坏情形:待排系列已按主要性字逆序
![](https://upload-images.jianshu.io/upload_images/1231308-40ade90dabea1fff.png)

最坏情况比较和移动次数.png
  • 平均意况:待排序恐怕现身的各个排列的票房价值一样
![](https://upload-images.jianshu.io/upload_images/1231308-240f3cb3a404b375.png)

平均情况比较和移动次数

* 冒泡排序的稳定性:是平静的排序方法。

空中复杂度 O(1)

  • 急需1个推推搡搡控件(监视哨),帮忙空间复杂度S(n)=O(1),此算法是就地排序

快快排序

算法思想:

高效排序
* 迅速排序是透过重庆大学字、调换记录,以某些记录为界(该记录称谓支点),将待排种类分成两某个。在那之中有的颇具记录的关键字大于支点记录的首要性字,另一局地持有记录的最首要字小于支点记录的最首要字。将待排连串按主要性字以支点记录分成两有个别的进度,称为二遍私分。对各部分不断划分,直到全体种类按主要性字有序,整个排序进度可以递归。

算法描述

设 1 <= p < q <= n ,r[p], r[p + 1],…,r[q]为待排体系

  • (1) low = p;high = q;
    r[0] = r[low]; // 取第八个记录为支点记录,low地点暂设为支点空位
  • (2) 若low = high, 支点空位鲜明,即为low
    r[low] = r[0];
    否则, low < high搜索供给沟通的笔录,并调换之。
  • (3)若low < high 且r[high].key >= r[0].key //
    从high所指向地方向前搜索,至多到low + 1 职位
    high = high – 1; 转3 // 寻找r[high].key < r[0].key
    r[low] = r[high]; // 找到r[high].key

未完待续

相关文章