Hill排序,归并排序的贯彻代码与思路
分类:www.澳门新萄京赌场

排序——插入排序,排序插入

#include <iostream>
using namespace std;

void InsertSort( int k[], int n )
{
    int i, j,temp;

    for( i=1; i < n;i   )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];

            for( j=i-1; k[j] > temp;j-- ) //找位置并且向后推移 
            {
                k[j 1] = k[j];
            }

            k[j 1] = temp;
        }
    }
}

int main()
{
    int i ,a[10] = {5,2,6,0,3,9,1,7,4,8};

    InsertSort(a,10);

    for( i=0; i < 10 ;i   )
    {
        cout << a[i];
    }

    cout << endl;

    return 0;
}

 

#include iostream using namespace std; void InsertSort( int k[], int n ){ int i, j,temp; for ( i= 1 ; i n;i ) { if ( k[i] k[i- 1 ] ) { tem...

计数排序是一种非相比的排序,这种办法思路大概是先算出待排序数据之中的数字分别出现些微次,然后再根据那几个寄放进新的数组里面,输出那几个数组,排序也就做到了。时间复杂度为o(n k),很三个人正是o(n),但实则只是近似而已。个中里面包车型地铁n是排序的数目个数,而k是排序中最大的值,总来说之,在n鲜明的场馆下,k的值越小,时间复杂度越低,比如即使n非常的小,但排序数是{2,5,3,一千0}的话,那也须要广大日子,此排序方法就有个别适用了。
前后相继例子:(首要参照相排版序主题措施,其余的写得相当不足好)
<pre><code>

Hill排序的面目就是分组插入排序,该办法又称减少增量排序。

用冒泡排序、接纳排序、插入排序、归并排序、火速排序、堆排序、Hill排序、计数排序写出上边这一题的代码

归并排序的兑今世码与思路,归并排序思路

第一考虑下怎么将将贰个不改变数列合併。那么些特别不难,只要从比较一个数列的第贰个数,何人小就先取哪个人,取了后就在对应数列中除去这一个数。然后再张开相比较,假设有数列为空,那直接将另三个数列的数量依次抽取就能够。

复制代码 代码如下:
View Code
 //将有序数组a[]和b[]合并到c[]中
 void MemeryArray(int a[], int n, int b[], int m, int c[])
 {
     int i, j, k;

     i = j = k = 0;
     while (i < n && j < m)
     {
         if (a[i] < b[j])
             c[k ] = a[i ];
         else
             c[k ] = b[j ];
     }

     while (i < n)
         c[k ] = a[i ];

     while (j < m)
         c[k ] = b[j ];
 }

能够观察合併有序数列的频率是相比高的,能够直达O(n)。

消除了上面包车型地铁统一有序数列难点,再来看归并排序,其的基本思路正是将数组分成二组A,B,假如那二组组内的数目都以铁定的事情的,那么就能够很实惠的将那二组数据开展排序。怎么样让那二组组内数据有序了?

能够将A,B组各自再分为二组。依次类推,当分出来的小组唯有多个数量时,能够以为那几个小组组内已经达成了平稳,然后再统一相邻的三个小组就足以了。这样经过先递归的表明数列,再统一数列就达成了归并排序。

复制代码 代码如下:
View Code
 //将有一个有序数列a[first...mid]和a[mid...last]合并。
 void mergearray(int a[], int first, int mid, int last, int temp[])
 {
     int i = first, j = mid 1;
     int m = mid,   n = last;
     int k = 0;

     while (i <= m && j <= n)
     {
         if (a[i] <= a[j])
             temp[k ] = a[i ];
         else
             temp[k ] = a[j ];
     }

     while (i <= m)
         temp[k ] = a[i ];

     while (j <= n)
         temp[k ] = a[j ];

     for (i = 0; i < k; i )
         a[first i] = temp[i];
 }
 void mergesort(int a[], int first, int last, int temp[])
 {
     if (first < last)
     {
         int mid = (first last) / 2;
         mergesort(a, first, mid, temp);    //左侧有序
         mergesort(a, mid 1, last, temp); //侧边有序
         mergearray(a, first, mid, last, temp); //再将二个不改变数列合併
     }
 }

 bool MergeSort(int a[], int n)
 {
     int *p = new int[n];
     if (p == NULL)
         return false;
     mergesort(a, 0, n - 1, p);
     delete[] p;
     return true;
 }

归并排序的频率是相比高的,设数列长为N,将数列分开成小数列一共要logN步,每步都以三个统一有序数列的经过,时间复杂度能够记为O(N),故一共为O(N*logN)。因为归并排序每一次都以在紧邻的数量中打开操作,所以归并排序在O(N*logN)的三种排序方法(飞速排序,归并排序,Hill排序,堆排序)也是作用相比高的

首先考虑下什么将将二个静止数列合併。那一个特别轻巧,只要从比较一个数列的率先个数,哪个人小...

include <iostream>

using namespace std;
//-------------------------
int data[100];//全局变量,用来存放待排序数据
int array_length;//数组的长度
int array_max;//数组中最大的值,也正是k
//---------------------------------
//开头化数组
void Init_array()
{
cout<<"Input:(End with 1000)";
for(int i=0;; i )
{
cin>>data[i];
if(data[i]==1000)
{
array_length = i;//由此获得数主任度
break;
}
}
}
//-----------------------------------
//求数组中最大的数
void max_array()
{
int t;
array_max = data[0];
for(int i=0; i<array_length-1; i)
{
if(data[i]<data[i 1])
{
array_max = data[i 1];
}
else
{
t = data[i];
data[i] = data[i 1];
data[i 1] = t;
}
}
}
//----------------------------------
//计数排序
//参数分别是1.待排序数组,2.数经理度,3.待排序数组中最大的值,也便是k
void sort_counter(int d[], int n, int k)
{
int i, j = 0,p = 0;
// 实际须要的空中比K大1
k ;
//支持数组,当然也足以用别的编制程序本事来顶替
int counter[100] = {0};
// 计数
for(i=0; i<n; i)
{
p = d[i];
counter[d[i]] ; //counter数组下标为排序的数,下标对应的数组值为这一个数现身的次数
}
//将计数结果保存到待排数据数组
for(i=0; i<k; i)
{
while(counter[i]-- > 0) //将出现的数字以及次数,依次停放数组中
{
d[j ] = i;
}
}
}
//主函数
int main(void)
{
Init_array();
max_array();
sort_counter(data, array_length-1, array_max);
int i;
for(i=0; i<array_length; i)
{
cout<<data[i]<<" ";
}
cout<<endl;
return 0;
}
</code></pre>

 

给定三个int数组A及数组的大小n,请回来排序后的数组。

该格局的中央思维是:先将全体待排成分体系分割成多少个头连串(由相隔某些“增量”的成分构成的)分别实行间接插入排序,然后依次缩减增量再扩充排序,待一切类别中的元素基本不改变(增量丰富小)时,再对总体成分进行三遍直接插入排序。因为直接插入排序在要素基本有序的状态下(相近最棒状态),功效是极高的,由此Hill排序在时间效能上比前三种办法有很大抓牢。

测量检验样例:
排序前[1,2,3,5,2,3],6
排序后[1,2,2,3,3,5]

 

1.冒泡排序
<code>
import java.util.*;
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i<n;i ){
for(int j=0;j<n-i-1;j ){
if(A[j]>A[j 1]){
int temp =A[j];
A[j] = A[j 1];
A[j 1] = temp;
}
}
}
return A;
}
}
</code>

以n=10的二个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

2.挑选排序
<code>
import java.util.*;
public class SelectSort {
public int[] selectionSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i<n-1;i ){
for(int j=i 1;j<n;j ){
if(A[i]<A[j]){
int temp =A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
return A;
}
}
</code>

第一次 gap = 10 / 2 = 5

3.插入排序
<code>
import java.util.*;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=1;i<n;i ){
for(int j=i;j>0;--j){
if(A[j]<A[j-1]){
int temp =A[j-1];
A[j-1] = A[j];
A[j] = temp;
}
}
}
return A;
}
}
</code>

49   38   65   97   26   13   27   49   55   4

4.归并排序
<code>
import java.util.*;
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int start = 0,end = n-1;
int[] copy = new int[n];//归并排序要求二个相助数组
merge(A,copy,start,end);
return A;
}
private void merge(int[] A, int[] copy, int start, int end){
if(start==end)
return;
int mid = (start end)>>1;
merge(A,copy,start,mid);
merge(A,copy,mid 1,end);
for(int i=start;i<=end;i )//先让帮忙数组跟原数组一样
copy[i] = A[i];
int id = start;
int m = start;
int n = mid 1;
while(m<=mid&&n<=end){
if(copy[m]<=copy[n]){
A[id ] = copy[m ];
}else{
A[id ] = copy[n ];
}
}
while(m<=mid)
A[id ] = copy[m ];
while(n<=end)
A[id ] = copy[n ];
}
}
</code>

1A                                        1B

5.飞跃排序
<code>
import java.util.*;
澳门新萄京,public class QuickSort {
public int[] quickSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int start = 0,end=n-1;
quick(A,start,end);
return A;
}
private void quick(int[] A, int start, int end){
if(start>=end)
return;
int key = A[start];//选用三个划分值
int i=start,j;
//假若这里成分小于划分值,则把此因素和i 1处成分调换,并将i加1,如当先或等于划分值则持续循环
for(j=start 1;j<=end;j ){
if(A[j]<key){
int temp = A[j];
A[j] = A[i 1];
A[i 1] = temp;
i ;
}
}
A[start] = A[i];
A[i] = key;
quick(A,start,i-1);
quick(A,i 1,end);
}
}
</code>

        2A                                         2B

6.堆排序
<code>
import java.util.;
public class HeapSort {
public int[] heapSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
for(int i=0;i<n-1;i ){
buildMaxHeap(A,n-1-i);
swap(A,0,n-1-i);
}
return A;
}
private void buildMaxHeap(int[] A, int lastIndex){//建大根堆
for(int i=(lastIndex-1)/2;i>=0;i--){//从lastIndex节点的父节点起首建堆
int k = i;//记录当前节点
while((2
k 1)<=lastIndex){//为各类节点创设大根堆,只要这一个根节点还恐怕有子节点
int bigIndex = 2*k 1;//假若左节点的值最大
if(bigIndex<lastIndex){//有右节点存在
//子节点中的最大值
if(A[bigIndex]<A[bigIndex 1])
bigIndex ;
}
//根节点跟子节点相比较
if(A[k]<A[bigIndex]){
swap(A,k,bigIndex);
k = bigIndex;
}
else
break;
}
}
}
private void swap(int[] A, int i, int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
</code>

                 3A                                         3B

7.Hill排序
<code>
import java.util.*;
public class ShellSort {
public int[] shellSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int increment,i,j,temp;
for(increment = n/2;increment>=1;increment/=2){//希尔排序的幅度逐步减小到1
for(i=increment;i<n;i ){//分组举办插入排序
temp = A[i];
for(j=i-increment;(j>=0)&&(A[j]>temp);j-=increment)
A[j increment] = A[j];
A[j increment] = temp;//前边小于待插入成分,设定待插入成分地点
}
}
return A;
}
}
</code>

                         4A                                          4B

8.计数排序
<code>
import java.util.*;
public class CountingSort {
public int[] countingSort(int[] A, int n) {
// write code here
if(null==A||n<=1)
return A;
int NUM = 999;
int[] B = new int[NUM];
for(int i=0;i<NUM;i )
B[i] = 0;//先让数组B中的成分全体为0
for(int i=0;i<n;i )
B[A[i]] ;
int k = -1;
for(int i=0; i<NUM;i ){
int j = B[i];
while(j>0){
k ;
A[k] = i;
j--;
}
}
return A;
}
}
</code>

                                  5A                                         5B

证实:前多个排序是岁月复杂度为O(n2),归并排序 飞速排序 堆排序 Hill排序的时日复杂度是O(NlogN),计数排序的日子复杂度为O(N)

1A,1B,2A,2B等为分组标识,数字同样的表示在同等组,大写字母表示是该组的第多少个要素, 每一遍对同样组的数量开展直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)那样每组排序后就改成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26),下同。

主题素材是对于以上的这一个标题,怎么样用java语言写出基数排序的代码?(计数排序和基数排序都不是依据比较的排序算法,二者的合计根源通排序)基数排序是先计划十二个桶(队列)依照个位10位百位步入相对应的0号到9号桶,然后倒出来就不改变了,代码怎么落实?

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A             1B             1C              1D            1E

        2A               2B             2C             2D              2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A   1B     1C    1D    1E      1F     1G    1H     1I     1J

第五次 gap = 1 / 2 = 0 排序实现获得数组:

4   13   26   27   38    49   49   55   65   97

 

上边给出严俊遵循定义来写的Hill排序

[cpp] view plain copy print?

  1. void shellsort1(int a[], int n)  
  2. {  
  3.     int i, j, gap;  
  4.   
  5.     for (gap = n / 2; gap > 0; gap /= 2) //步长   
  6.         for (i = 0; i < gap; i )        //直接插入排序   
  7.         {  
  8.             for (j = i   gap; j < n; j  = gap)   
  9.                 if (a[j] < a[j - gap])  
  10.                 {  
  11.                     int temp = a[j];  
  12.                     int k = j - gap;  
  13.                     while (k >= 0 && a[k] > temp)  
  14.                     {  
  15.                         a[k   gap] = a[k];  
  16.                         k -= gap;  
  17.                     }  
  18.                     a[k   gap] = temp;  
  19.                 }  
  20.         }  
  21. }  

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

    int i, j, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2) //步长
        for (i = 0; i < gap; i  )        //直接插入排序
        {
            for (j = i   gap; j < n; j  = gap) 
                if (a[j] < a[j - gap])
                {
                    int temp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > temp)
                    {
                        a[k   gap] = a[k];
                        k -= gap;
                    }
                    a[k   gap] = temp;
                }
        }
    

    }

很鲜明,下面的shellsort1代码固然对直观的驾驭希尔排序有辅助,但代码量太大了,远远不够简洁清晰。因而开展下革新和优化,以第一回排序为例,原本是历次从1A到1E,从2A到2E,能够改成从1B开班,先和1A相比,然后取2B与2A相比,再取1C与前面自个儿组内的数据相比较…….。这种每便从数组第gap个成分初阶,每种成分与协和组内的数目举行直接插入排序显著也是不错的。

[cpp] view plain copy print?

  1. void shellsort2(int a[], int n)  
  2. {  
  3.     int j, gap;  
  4.       
  5.     for (gap = n / 2; gap > 0; gap /= 2)  
  6.         for (j = gap; j < n; j )//从数组第gap个因素早先   
  7.             if (a[j] < a[j - gap])//各种元素与和煦组内的数额开展直接插入排序   
  8. Hill排序,归并排序的贯彻代码与思路。            {  
  9.                 int temp = a[j];  
  10.                 int k = j - gap;  
  11.                 while (k >= 0 && a[k] > temp)  
  12.                 {  
  13.                     a[k   gap] = a[k];  
  14.                     k -= gap;  
  15.                 }  
  16.                 a[k   gap] = temp;  
  17.             }  
  18. }  

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

    int j, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2)
        for (j = gap; j < n; j  )//从数组第gap个元素开始
            if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
            {
                int temp = a[j];
                int k = j - gap;
                while (k >= 0 && a[k] > temp)
                {
                    a[k   gap] = a[k];
                    k -= gap;
                }
                a[k   gap] = temp;
            }
    

    }

再将直接插入排序部分用 白话杰出算法类别之二 直接插入排序的三种实现  中央市直机关接插入排序的第三种方式来改写下:

[cpp] view plain copy print?

  1. void shellsort3(int a[], int n)  
  2. {  
  3.     int i, j, gap;  
  4.   
  5.     for (gap = n / 2; gap > 0; gap /= 2)  
  6.         for (i = gap; i < n; i )  
  7.             for (j = i - gap; j >= 0 && a[j] > a[j   gap]; j -= gap)  
  8.                 Swap(a[j], a[j   gap]);  
  9. }  

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

    int i, j, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i  )
            for (j = i - gap; j >= 0 && a[j] > a[j   gap]; j -= gap)
                Swap(a[j], a[j   gap]);
    

    }

这么代码就变得不得了简单了。

  

附注:上面Hill排序的增幅选用都以从n/2起先,每一回再减半,直到最终为1。

本文由澳门新萄京发布于www.澳门新萄京赌场,转载请注明出处:Hill排序,归并排序的贯彻代码与思路

上一篇:澳门新萄京习题汇总,C语言基础 下一篇:没有了
猜你喜欢
热门排行
精彩图文