C语言代码实现,好大学慕课台湾高校陈越先生、何钦铭先生的《数据结构》

本文重要介绍排序的三种实现,简单总结一下复杂度。

本博客的代码的思考和图片参考:好大学慕课山东高校陈越先生、何钦铭先生的《数据结构》

  1. 冒泡排序

 


排序

  void BubbleSort(ElementType A[],int N)
  {
      int P,flag;
      for(P = N-1;P>=0;p--)
      {
        flag = 0;/*建立一个检查标志:在某次排序提前完成后终止循环*/
        for(int i=0;i < p;i++)/*一趟冒泡*/
        {
            if(A[i]>A[i+1])
            {
                  swap(A[i],A[i+1]);
                  flag = 1;
              }
          }
          if (flag = 0) break;
      }
  }/*冒泡排序*/

1 排序前提

1.函数的称呼正式

void X_Sort ( ElementType
A[], int N )

2.大部分动静下,为简单起见,琢磨从小大的平头排序

3.N是正整数

4只谈谈基于相比较的排序( >= <
有定义 )

5.只谈谈其中排序

6稳定:任意六个异常的多寡,排序前后的周旋地点不暴发变更

7.平素不一种排序是另外动静下都突显最好的

  1. 插入排序

1 冒泡排序


1.1算法思想

先是趟:相比首个要素和第二元素,倘若第一个因素比第二个因素大,就交换地点,否则就不交流地点;在相比第二元素和第两个元素的轻重,倘使第二个因素比第两个因素大,互换地点,否则不互换地方;然后跟着相比较第几个元素和第多少个元素……
直到相比到第N-1个因素和第N个因素。这样一趟下来,能够规定最大的元素在N地方

第二趟:相比第一个要素和第二要素,假诺第一个元素比第二个元素大,就互换地方,否则就不互换地点;在相比较第二要素和第六个元素的大小,假诺第二个因素比第三个因素大,交流地点,否则不互换地点;然后随着相比第多少个元素和第多少个因素……,直到比较到N-2
和N-1个要素。这样,第二趟上面,第二大的元素得以规定在N-1地点。

第三趟……

如此这般到第N趟,就足以吧数组排序完成。

N-1趟排序组成
C语言代码实现:

1.2 伪代码描述

/*

* A method to implement
bubble sort.If the bubble sort has no any swap

* operation at one
time,indicating the array has been ordered.So we use
a

* tag to make it
effective

*@param a A integer array need to
sort

*@param n The length of the
array

*/

void**bubble_sort(elementType a[],int** n)
{

int i, j,
flag;

for (i = n –
1; i >= 0; i–) {

flag =
0;

for (j = 0; j
< i; j++) {

if (a[j]
> a[j + 1]) {

swap(&a[j],
&a[j + 1]);

flag =
1;

}

}

if (flag ==
0) {

break;

}

}

}

void(InsertionSort)(ElementType A[],int N)
{
  int j,P;
  ElementType tmp;
  for(P=1;P<N;P++)
{
    tmp = A[P];/*摸下一张牌*/
    for(j = P; j>0&&A[j-1]>tmp; j--)
        A[j] = A[j-1];/*移出空位*/
    A[j] = tmp;/*新牌落位*/
 }
}/*插入排序例程*/

1.3 算法分析

最好的情状:即便这多少个数组本身就是平稳的,那么时间复杂:T=O(N)

最坏的场合:借使这个数组本身就是逆序的,那么时间复杂度为T=O(N^2)

因为只有当前面的元素严酷的大于前边元素时,才会换换地方,相对地方不会发出转移,那么该算法是平安无事的。

插入排序为O(N^2)
N个互异数的数组的平分逆序数是N(N-1)/4

2 采取排序

  1. Hill排序-缩短增量排序

2.1算法思想

分选排序的前提是保险数组中已有元素是不变的。例如在给数组的第i个元素排序(找合适岗位)时,已经保证前边i-1个因素是雷打不动的。

首先趟:当给数组中首先个因素排序时,因为就一个要素,默认就是一动不动的。

其次趟:当给数组中第二元素排序时,相比(前一个因素)第一个因素是否比他大,如若大,把前一个要素将来头摞一位,然后。

其三趟:给数组中第六个要素排序时,比较前一个要素是不是比他大,比他大,前一个元素向后摞一位。在相比较在前头一个因素是否比他大,假若比他大,在啊在前一个元素将来摞一位;假如不比他大,那么刚才分外摞的百般空位就就放入该因素。

第四趟……

第N趟


2.2 伪代码描述

/*

*
Implemet insertion
sort.

*@param a A
integer array need to sort

*@param n The
length of the array

*/

void**insertion_sort(elementType a[],int** n)
{

int i,
j;

elementType
temp;

for (i = 1; i
< n; i++) {

temp =
a[i];

for (j = i; j
> 0 && a[j – 1] > temp; j–)
{

a[j] = a[j –
1];

}

a[j] =
temp;

}

}

考虑:把记录按步长 gap
分组,对每组记录采纳直接插入排序方法开展排序。随着步长逐渐减小,所分成的组包含的笔录越来越多,当步长的值减小到
1 时,整个数据合成为一组,构成一组有序记录,则完成排序。
直接插入排序和Hill排序的可比:

2.3 算法分析

最好的情景:即便这一个数组本身就是一成不变的,那么时间复杂:T=O(N)

最坏的气象:假设这些数组本身就是逆序的,那么时间复杂度为T=O(N^2)

因为只有当前边的要素严酷的大于前边元素时,才会换成地方,相对地点不会发生变动,那么该算法是平静的。

  1. 直接插入排序是祥和的;而Hill排序是不安静的。
  2. 间接插入排序更适合于原始记录基本平稳的汇集。
  3. 希尔(Hill)排序的相比较次数和活动次数都要比直接插入排序少,当N越大时,效果越显著。
  4. 在Hill排序中,增量体系gap的模拟必须满意:最终一个幅度必须是 1 。
  5. 直接插入排序也适用于链式存储结构;希尔(Hill)排序不适用于链式结构。

3 时间复杂的下界

为了证实这个题目,我先提交一个例题:

给定开端类别{34, 8, 64, 51,32,
21},冒泡排序和插入排序分别需要有些次元素交流才能到位?

答:冒泡需要9次,拔取排序也亟需9次。这是一个偶合吗?

希尔排序.png

3.1 引入概念

对于下标i<j,假若A[i]>A[j],则称(i,j)是一对逆序对(inversion)

题材:体系{34, 8, 64, 51, 32,
21}中有稍许逆序对?

(34, 8) (34, 32) (34, 21)
(64, 51) (64, 32) (64, 21) (51, 32) (51, 21) (32,
21)

有九个逆序对。

换成多少个相邻的逆序对刚刚消去一个逆序对!

插入排序(冒泡排序)的年月复杂度可以重复定义为:

T(N,I)=O(N,I).I为N个要素中逆序对的个数

——倘使需要排序的行列基本平稳,则插入排序简单且高效

C语言代码实现:

3.2 时间复杂度下界

定理:任意N个不同因素结合的行列平均具有N ( N – 1 ) / 4
个逆序对。

定理:任何仅以互换相邻两元一向排序的算

法,其平均时间复杂度为 ( N^2 )

这象征:要提高算法效能,大家必须

1.老是消去不止1个逆序对!

2.
每回互换相隔较远的2个元素!

void Shellsort(ElementType A[],int N)
{
int i,j,Increment;
ElementType tmp;
for (Increment = N/2; Increment>0; Increment/=2)
for ( i = Increment; i < N; i++)
{
  tmp = A[i];
  for ( j = i; j >= Increment; j-=Increment)
       if(tmp<A[j - Increment)
      A[j] = A[j- Increment];
    else
      break;
  A[j] = tmp;
  }
}/*使用希尔增量的希尔排序例程*/

4 希尔排序

Java代码贯彻:

4.1算法思想

概念增量系列 D M > D M-1 > …
> D 1 = 1

对每个 D k
进行“D k
-间隔”排序 ( k = M, M-1, … 1
)

小心:“D k
-间隔”有序的队列,在履行“D k-1
-间隔”排序后,依然是“D k –

间隔”有序的。上面用一幅图片来表明希尔(Hill)排序的历程

365体育官网 1

 

 

package notes.javase.algorithm.sort;
public class ShellSort {
public void shellSort(int[] list) {
    int gap = list.length / 2;
 while (1 <= gap) {
        // 把距离为 gap 的元素编为一个组,扫描所有组
        for (int i = gap; i < list.length; i++) {
            int j = 0;
            int temp = list[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        System.out.format("gap = %d:\t", gap);
        printAll(list);
        gap = gap / 2; // 减小增量
    }
}
// 打印完整序列
public void printAll(int[] list) {
    for (int value : list) {
        System.out.print(value + "\t");
    }
    System.out.println();
}
public static void main(String[] args) {
    int[] array = {
            9, 1, 2, 5, 7, 4, 8, 6, 3, 5
    };
    // 调用希尔排序方法
    ShellSort shell = new ShellSort();
    System.out.print("排序前:\t\t");
    shell.printAll(array);
    shell.shellSort(array);
    System.out.print("排序后:\t\t");
    shell.printAll(array);
 }
}

4.2希尔(Hill)排序的伪代码描述

  1. 堆排序

4.2.1骨干的Hill排序的伪代码

/*

* Implement base shell
sort

*@param a A
integer array need to sort

*@param n The
length of the array

*/

void**shell_sort_base(elementType a[],int** n)
{

int i, j,
d;

elementType
temp;

for (d = n /
2; d > 0; d = d / 2) {

for (i = d; i
< n; i++) {

temp =
a[i];

for (j = i; j
>= d && a[j – d] > temp; j -= d)
{

a[j] = a[j –
d];

}

a[j] =
temp;

}

}

}

在核心的希尔(Hill)排序中,我们的距离取 n/2 n/4 n/8 … n/2^i …
1

在上头基本的希尔(Hill)排序中,最坏的大运复杂度T(n)=O(n^2).很糟糕

上边举一个最坏意况的例证

365体育官网 2


4.3 希尔(Hill)排序的增量连串

365体育官网 3

 

基本措施:确立N个元素的二叉堆,花费时间O(N),然后实施N次DeletedMin操作花费时间O(log⁡N),所以总的运行时刻为O(N log⁡N)
缺点:DeleteMin操作中行使了一个数组用来囤积离开堆得元素,所以存储需求扩展一倍。
C语言代码实现:
#define LeftChild(i)(2*(i)+1)
void
PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType tmp;
for(tmp = A[i];LeftChild(i)<N;i = Child)
{
Child = LeftChild(i);
if(Child!=N-1&&A[Child + 1]>A[Child])
Child++;
if(tmp<A[Child])
A[i] = A[Child];
else
break;
}
A[i] = tmp;
}
void Heapsort(ElementType A[],int N)
{
int i;
for(i = N/2;i>=0;i–)
PercDown(A,i,N);
for(i = N-1;i >0;i–)
{
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}

5 堆排序

Sorting_heapsort_anim.gif

5.1 引子

在介绍堆排序从前,大家先介绍一下选拔排序。

选料排序的算法思想:第一次从N个元素中采取一个小小的。放入0地方,第二次从N个元素中挑选第二小的,放入1职位。… 第i次从N个元素采用第i小的因素放入第i-1地点

下面是选项排序的伪代码描述

void Selection_Sort (
ElementType A[], int N )

{

for ( i = 0; i < N; i
++ ) {

MinPosition = ScanForMin(
A, i, N–1 );

/*
从A[i]到A[N–1]中找最小元,并将其岗位赋给MinPosition
*/

Swap( A[i],
A[MinPosition] );

/*
将未排序部分的纤维元换到平稳部分的末段地方 */

}

}

对此交流元素的操作,是线性。问题在于从N个元素每便找到最i小的因素。拔取排序相比较暴力,他老是都是从N个元素中挑选最小的要素,然后开展置换地点。这样时间时间复杂度T(N)=O(N^2).我们只要立异找到最小元的操作?

答案是应用我们从前学过的工具,最小堆。

  1. 归并排序

5.2 堆排序算法1—施用最小堆

算法思想:把用户给定的数组调整成一个小小的堆,每一回从堆中弹出一个小小的的因素,使用临时数组保存,然后在吗临时数组的要素复制回原数组。

伪代码描述:

void Heap_Sort (
ElementType A[], int N )

{

BuildHeap(A); /* O(N)
*/

for ( i=0; i<N; i++
)

TmpA[i] = DeleteMin(A);
/* O(logN) */

for ( i=0; i<N; i++ )
/* O(N) */

A[i] =
TmpA[i];

}

经过伪代码大家得以观察,此算法的刻钟复杂的度为T(N)=O(NlogN),可是他索要开辟一个临时的数组O(N)来存放已经排序好的因素。而且还修养话费元素复制的日子。


5.3 堆排序算法2—选拔最大堆

算法思想:首先吧数组调整成最大堆。把最大堆的第一个元素和末段一个因素交替地方。这样最大的因素就在原数组的末段。然后呢剩下n-1个元素调整成最大堆。重复下边的操作。这样每一次选出最大的要素。

伪代码描述:

void Heap_Sort (
ElementType A[], int N )

{

for ( i=N/2-1; i>=0;
i– )/* BuildHeap */

PercDown( A, i, N
);

for ( i=N-1; i>0; i– )
{

Swap( &A[0], &A[i] );
/* DeleteMax */

PercDown( A, 0, i
);

}

}

归并排序以O(NlogN)最坏意况运行时刻运作,而所利用的相比次数几乎是最优的。是递归算法的一个很好的实例。分治是递归非凡强大的用法。

5.3 算法分析

1.定律:堆排序处理N个不同因素的轻易排列的平分比较次数是2N logN – O(Nlog logN)

2.即使堆排序给出最佳平均时间复杂度,但实际效果不如用Sedgewick增量体系的Hill排序。

3.堆排序好处是取出前i个不大的数。

void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
int Center;
if(Left<Right)
  {
        Center = (Left + Right)/2;
        MSort(A,TmpArray,Left,Center);
        MSort(A,TmpArray,Center+1,Right);
        Merge(A,TmpArray,Left,Center+1,Right);
  }
}

void Mergesort(ElementType A[],int N)
{
      ElementType *TmpArray;
      TmpArray = malloc(N*sizeof(ElementType));
      if(TmpArray != NULL)
     {
      MSort(A,TmpArray,0,N-1);
      free(TmpArray);
     }
     else
    FatalError("No space for tmp array!");
}/*归并排序例程*/

6 归并排序

Merge_sort_animation2.gif

6.1有序子列归并

在介绍归并排序的算法从前,我们先来介绍一下“有序子列的合并”下面通过一张图片来介绍

 

365体育官网 4

 

上边是交由有序子列归并的源代码

/*

* Merge sub-sequence to
original array.

*
@param a
original <code>elementType</code> array to store the
elements

*
@param tmpA
temporary <code>elementType</code> array to store the
temporary elements

*
@param l The
start index of left
sub-sequence

*
@param r The
start index of left
sub-sequence

*
@param rightEnd
The end index of left
sub-sequence

*/

void**merge(elementType a[],elementType tmpA[],int l,int r,int** rightEnd)
{

/*

* lefeEnd is the r-1,the
sub-sequence is adjacent

*/

int leftEnd =
r – 1;

/*

*
tmp is the
counter of the
<code>tmpA</code>

* we should let
<code>tmpA</code> index corresponding original
array

*/

int tmp =
l;

/*

* Record the quantity of
the all elements

*/

int
numElements = rightEnd – l +
1;

int
i;

while (l <=
leftEnd && r <= rightEnd) {

if (a[l]
<= a[r]) {

tmpA[tmp++] = a[l++];

}
365体育官网,else
{

tmpA[tmp++] = a[r++];

}

}

while (l <=
leftEnd) {

tmpA[tmp++] = a[l++];

}

while (r <
rightEnd) {

tmpA[tmp++] = a[r++];

}

/*

* Put
<code>tmpA</code> elements into the original
array

*/

for (i = 0; i
< numElements; i++, rightEnd–)
{

a[rightEnd] =
tmpA[rightEnd];

}

}

这么些代码的时刻复杂度在地点已经说过了,为T(N)=O(N)

问题:因为联合多少个排序的表需要线性附加内存,在全方位算法中还要花费将数据拷贝到临时数组再拷贝回来这么一些增大工作,其结果严重播慢了排序的速度。所以很难用于主存排序。

6.2 递归算法的递归实现365体育官网 5

 

这多少个时刻复杂的从未有过最好,最坏,平均。不论什么的行列,都是NlogN的光阴复杂度。

  1. 高速排序

6.3 递归算法中的临时数组问题

在归并排序中,我们选拔到一个暂时数组,那么那些临时数组在哪个地方分配相比较客观?

考虑一下,假若我们在merge函数中申请,这会如何啊。这就会冒出,没调用五遍merge函数,我们需要申请和自由这样的一个暂时数组。这样申请假释的操作如下图所示:

365体育官网 6

诸如此类会平凡的对内存实行报名和自由,是很不划算的,而且最终如故要申请一个和N一样大学的数组,那么大家还不如自己在接口函数中把她直接定义好。如下图所示:

365体育官网 7

 

 

虽然大家在一上马归并经过中只会用到临时数组的一小部分,不过总比每便申请假释来的经济。


6.4 归并排序的非递归实现

我们清楚递归算法是很耗费系统的库房,而且很容易导致内存的溢出。所以大家下边我们采取非递归的主意来落实归并排序。

非递归算法的沉思是一起头对数组两两开展统一,然后对六个元素结合的成团在拓展两两归并。最终成功数组的排序。下面接纳图片来验证

365体育官网 8

 

连忙排序是在实践中最快的已知排序算法,它的平分运行时刻为O(NlogN)。该算法相当快的来由是这些简便和惊人优化的里边循环。最坏意况的属性为O(N^2),但稍加努力就可以避免。
三数中值分割法:扫除了预排序输入的坏意况,并且减弱了便捷排序大约5%的运行时刻。
对于很小的数组(N<=20)不递归地应用高效排序,而代之以诸如插入排序这种对小数组有效的排序算法。
算法步骤:

6.4.1 非递归归并排序的伪代码描述

  1. 从数列中挑出一个元素,称为 “基准”(pivot)。
  2. 重复排序数列,所有因素比基准值小的摆放在基准前面,所有因素比基准值大的摆在基准的背后(相同的数可以到任一边)。在那些分区退出之后,该原则就高居数列的中游地方。这些叫做分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和超过基准值元素的子数列排序。

/*

* Use loop method to
implement the merge sort

*
@param a A
integer array need to sort

*
@param n The
length of the array

*/

void**merger_SortLoop(elementType a[],int** n)
{

int
length;

elementType
*tmpA;

length =
1;

tmpA =
malloc(n *
sizeof(elementType));

if
(tmpA != NULL)
{

while (length
< n) {

/*

* merge ordered
sub-sequence into
<code>tmpA</code>

*/

mergerPass(a,
tmpA, n,
length);

length
*= 2;

/*

* merge ordered
sub-sequence from <code>tmpA</code> into
<code>a</code>

*/

mergerPass(tmpA, a, n,
length);

length
*= 2;

}

free(tmpA);

}
else
{

printf(“no
enough to apply for temporary
array”);

}

}

7 各样排序算法在PAT的测试结果

  void Quicksort(ElementType A[],int N)
{
    Qsort(A,0,N-1);
}

ElementType Median3(ElementType A[],int Left,int Right)
{
    int Center = (Left + Right)/2;
    if(A[Left]>A[Center])
        Swap(&A[Left],&A[Center]);
    if(A[Left]>A[Right])
        Swap(&A[Left],&A[Right]);
    if(A[Center]>A[Right])
        Swap(&A[Center],&A[Right]);
    Swap(&A[Center],&A[Right-1]);
    return A[Right-1];
}/*实现三数中值分割方法的程序*/


#define Cutoff(3)
void Qsort(ElementType A[],int Left,int Right)
{
    int i,j;
    ElementType Pivot;
    if(Left+Cutoff <=Right)
    {
        Pivot = Median3(A,Left,Right);
        i = Left;j = Right-1;
        for( : : )
        {
            while(A[++j]<Pivot){}
            while(A[--j]>Pivot){}
            if(i<j)
                Swap(&A[i],&A[j]);
            else
                break;
        }
        Swap(&A[i],&A[Right-1]);
        Qsort(A,Left,i-1);
        Qsort(A,i+1,Right);
    }
    else
        InsertionSort(A+Left,Right - Left + 1);
  }/*快速排序的主例程序*/

7.1测试题测试样例

给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果。

核心意在测试各样不同的排序算法在各类数码情形下的展现。各组测试数据特点如下:

  • 数据1:只有1个元素;

  • 数据2:11个不等同的整数,测试大旨科学;

  • 数据3:103个随机整数;

  • 数据4:104个随机整数;

  • 数据5:105个随机整数;

  • 数据6:105个顺序整数;

  • 数据7:105个逆序整数;

  • 数据8:105个为主平稳的平头;

  • 数据9:105个随机正整数,每个数字不超过1000。

Sorting_quicksort_anim.gif

输入格式:

输入第一行提交正整数N(≤10​5​​),随后一行给出N个(长整型范围内的)整数,其间以空格分隔。

参考:

1.
程序员必须清楚的10大基础实用算法及其讲解

2. 排序四
Hill排序

输出格式:

在一行中输出从小到大排序后的结果,数字间以1个空格分隔,行末不得有剩余空格。

输入样例:

11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 98

7.2冒泡排序的测试结果

365体育官网 9

 

7.3插入排序测试结果

365体育官网 10

 

7.4 堆排序的测试结果

365体育官网 11

7.5希尔(Hill)排序的测试结果

365体育官网 12

只是Hill排序也有经过的事例

365体育官网 13

 

7.6 归并排序递归算法测试结果

365体育官网 14

7.7 归并算法非递归算法的测试结果

365体育官网 15

 

 

7.8 结果分析

从上边的测试结果来看,堆排序,归并排序都完美通过了测试,而且效率挺高的。

冒泡排序没有经过测试很正常,因为时间复杂度为O(N^2).

是本人深感惊愕的是,插入排序居然通过了测试,尽管挺耗时,不过Hill排序在测试点7:105个逆序整数竟然从未经过。我的希尔排序使用Sedgewick系列。不是理论上是O(N^(4/3)),怎么会并未经过呢。可是日子复杂度和冒泡排序相近的插入排序居然通过了。好想得到。而且插入排序在测试点7:105个逆序整数全体是逆序数最坏的时间复杂度为O(N^2),怎么就通过了吗。好想拿到。后来一再对Hill排序举行测试,发现有时候能够透过,有时候没有通过,揣测是受机器的震慑。感觉Hill排序效用不高,平均的都在5000ms以上

 

 

8各个排序的源代码

 

365体育官网 16365体育官网 17

 1 /*
 2  * bubbleSort.c
 3  *
 4  *  Created on: 2017年5月18日
 5  *      Author: ygh
 6  */
 7 
 8 #include <stdio.h>
 9 
10 typedef int elementType;
11 #define  MAX_LENGTH 100000
12 
13 /*
14  * Swap two integer number value
15  */
16 void swap(elementType *a, elementType *b) {
17     int temp = *b;
18     *b = *a;
19     *a = temp;
20 }
21 /*
22  * A method to implement bubble sort.If the bubble sort has no any swap
23  * operation at one time,indicating the array has been ordered.So we use a
24  * tag to make it effective
25  *@param a A integer array need to sort
26  *@param n The length of the array
27  */
28 void bubble_sort(elementType a[], int n) {
29     int i, j, flag;
30     for (i = n - 1; i >= 0; i--) {
31         flag = 0;
32         for (j = 0; j < i; j++) {
33             if (a[j] > a[j + 1]) {
34                 swap(&a[j], &a[j + 1]);
35                 flag = 1;
36             }
37         }
38         if (flag == 0) {
39             break;
40         }
41     }
42 }
43 
44 /*
45  * Print the array to console
46  * @param a A integer array need to sort
47  * @param n The length of the array
48  */
49 void printArray(int a[], int n) {
50     int i;
51     for (i = 0; i < n; i++) {
52         if (i == n - 1) {
53             printf("%d", a[i]);
54         } else {
55             printf("%d ", a[i]);
56         }
57     }
58     printf("\n");
59 }
60 
61 /*
62  * Get input data from command
63  */
64 void getInputData(elementType *a, int n) {
65     int i;
66     elementType x;
67     for (i = 0; i < n; i++) {
68         scanf("%d", &x);
69         a[i] = x;
70     }
71 }
72 
73 int main() {
74     int a[MAX_LENGTH];
75     int n;
76     scanf("%d", &n);
77     getInputData(a, n);
78     bubble_sort(a, n);
79     printArray(a, n);
80     return 0;
81 }

Bubble_Sort

 

 

365体育官网 18365体育官网 19

 1 /*
 2  * insertionSort.c
 3  *
 4  *  Created on: 2017年5月18日
 5  *      Author: ygh
 6  */
 7 
 8 #include <stdio.h>
 9 
10 #define  MAX_LENGTH 100000
11 typedef int elementType;
12 
13 /*
14  * Swap two integer number value
15  */
16 void swap(elementType *a, elementType *b) {
17     int temp = *b;
18     *b = *a;
19     *a = temp;
20 }
21 /*
22  * Implement insertion sort.
23  *@param a A integer array need to sort
24  *@param n The length of the array
25  */
26 void insertion_sort(elementType a[], int n) {
27     int i, j;
28     elementType temp;
29     for (i = 1; i < n; i++) {
30         temp = a[i];
31         for (j = i; j > 0 && a[j - 1] > temp; j--) {
32             a[j] = a[j - 1];
33         }
34         a[j] = temp;
35     }
36 
37 }
38 
39 /*
40  * Print the array to console
41  * @param a A integer array need to sort
42  * @param n The length of the array
43  */
44 void printArray(int a[], int n) {
45     int i;
46     for (i = 0; i < n; i++) {
47         if (i == n - 1) {
48             printf("%d", a[i]);
49         } else {
50             printf("%d ", a[i]);
51         }
52     }
53     printf("\n");
54 }
55 
56 /*
57  * Get input data from command
58  */
59 void getInputData(elementType *a, int n) {
60     int i;
61     elementType x;
62     for (i = 0; i < n; i++) {
63         scanf("%d", &x);
64         a[i] = x;
65     }
66 }
67 
68 int main() {
69     int a[MAX_LENGTH];
70     int n;
71     scanf("%d", &n);
72     getInputData(a, n);
73     insertion_sort(a, n);
74     printArray(a, n);
75     return 0;
76 }

Insertion_Sort

 

365体育官网 20365体育官网 21

  1 /*
  2  * shellSort.c
  3  *
  4  *  Created on: 2017年5月18日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 #include <math.h>
 10 
 11 #define  MAX_LENGTH 100000
 12 typedef int elementType;
 13 
 14 /*
 15  * Swap two integer number value
 16  */
 17 void swap(elementType *a, elementType *b) {
 18     int temp = *b;
 19     *b = *a;
 20     *a = temp;
 21 }
 22 
 23 int getSedgewickStep(int *step, int n) {
 24     int i, v1, v2, counter = 0;
 25     i = 0;
 26     for (i = 0; i < n; i++) {
 27         v1 = 9 * pow(4, i) - 9 * pow(2, i) + 1;
 28         if (v1 > 0 && v1 < n) {
 29             step[counter++] = v1;
 30         }
 31         v2 = pow(4, i) - 3 * pow(2, i) + 1;
 32         if (v2 > 0 && v2 < n) {
 33             step[counter++] = v2;
 34         }
 35         if (v1 > n && v2 > n) {
 36             break;
 37         }
 38     }
 39     return counter;
 40 }
 41 
 42 /*
 43  * A method to implement bubble sort.If the bubble sort has no any swap
 44  * operation at one time,indicating the array has been ordered.So we use a
 45  * tag to make it effective
 46  *@param a A integer array need to sort
 47  *@param n The length of the array
 48  */
 49 void bubble_sort(int a[], int n) {
 50     int i, j, flag;
 51     for (i = n - 1; i >= 0; i--) {
 52         flag = 0;
 53         for (j = 0; j < i; j++) {
 54             if (a[j] > a[j + 1]) {
 55                 swap(&a[j], &a[j + 1]);
 56                 flag = 1;
 57             }
 58         }
 59         if (flag == 0) {
 60             break;
 61         }
 62     }
 63 }
 64 
 65 /*
 66  * Implement base shell sort
 67  *@param a A integer array need to sort
 68  *@param n The length of the array
 69  */
 70 void shell_sort_expand_Sedgewick(elementType a[], int n) {
 71     int i, j, d, counter, step;
 72     elementType temp;
 73     int sequence[] = { 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,
 74             16001, 6289, 64769 };
 75     counter = 13;
 76     /*int sequence[n / 2];
 77      counter = getSedgewickStep(sequence, n);
 78      bubble_sort(sequence, counter);*/
 79     /*printArray(sequence, counter);
 80      return;*/
 81     for (d = 0; d < counter && sequence[d] < n; d++) {
 82         step = sequence[d];
 83         for (i = step; i < n; i++) {
 84             temp = a[i];
 85             for (j = i; j >= step && a[j - step] > temp; j -= step) {
 86                 a[j] = a[j - step];
 87             }
 88             a[j] = temp;
 89         }
 90     }
 91 
 92 }
 93 
 94 /*
 95  * Implement base shell sort
 96  *@param a A integer array need to sort
 97  *@param n The length of the array
 98  */
 99 void shell_sort_expand_Sedgewick2(elementType a[], int n) {
100     int i, j, d, counter, step;
101     elementType temp;
102     int sequence[n / 2];
103     counter = getSedgewickStep(sequence, n);
104     bubble_sort(sequence, counter);
105     for (d = 0; d < counter && sequence[d] < n; d++) {
106         step = sequence[d];
107         for (i = step; i < n; i++) {
108             temp = a[i];
109             for (j = i; j >= step && a[j - step] > temp; j -= step) {
110                 a[j] = a[j - step];
111             }
112             a[j] = temp;
113         }
114     }
115 
116 }
117 
118 /*
119  * Implement base shell sort
120  *@param a A integer array need to sort
121  *@param n The length of the array
122  */
123 void shell_sort_base(elementType a[], int n) {
124     int i, j, d;
125     elementType temp;
126     for (d = n / 2; d > 0; d = d / 2) {
127         for (i = d; i < n; i++) {
128             temp = a[i];
129             for (j = i; j >= d && a[j - d] > temp; j -= d) {
130                 a[j] = a[j - d];
131             }
132             a[j] = temp;
133         }
134     }
135 
136 }
137 
138 /*
139  * Print the array to console
140  * @param a A integer array need to sort
141  * @param n The length of the array
142  */
143 void printArray(int a[], int n) {
144     int i;
145     for (i = 0; i < n; i++) {
146         if (i == n - 1) {
147             printf("%d", a[i]);
148         } else {
149             printf("%d ", a[i]);
150         }
151     }
152     printf("\n");
153 }
154 
155 /*
156  * Get input data from command
157  */
158 void getInputData(elementType *a, int n) {
159     int i;
160     elementType x;
161     for (i = 0; i < n; i++) {
162         scanf("%d", &x);
163         a[i] = x;
164     }
165 }
166 
167 int main() {
168     int a[MAX_LENGTH];
169     int n;
170     scanf("%d", &n);
171     getInputData(a, n);
172     shell_sort_expand_Sedgewick2(a, n);
173     printArray(a, n);
174     return 0;
175 }

Shell_Sort

 

365体育官网 22365体育官网 23

  1 /*
  2  * heapSort.c
  3  *
  4  *  Created on: 2017年5月18日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 
 10 #define  MAX_LENGTH 100000
 11 typedef int elementType;
 12 
 13 /*
 14  * Swap two integer number value
 15  */
 16 void swap(elementType *a, elementType *b) {
 17     int temp = *b;
 18     *b = *a;
 19     *a = temp;
 20 }
 21 
 22 /*
 23  * Update the element of tree make the tree to be a maximal heap
 24  * @param a A <code>elementType</code> array to store the elements
 25  * @param p The index of the element need to update
 26  * @param n The length of the array
 27  */
 28 void percDowm(elementType a[], int p, int n) {
 29     int parent, child;
 30     elementType x;
 31     x = a[p];
 32     for (parent = p; (parent * 2 + 1) < n; parent = child) {
 33         child = parent * 2 + 1;
 34         if ((child != n - 1) && a[child] < a[child + 1]) {
 35             child++;
 36         }
 37         if (x >= a[child]) {
 38             break;
 39         } else {
 40             a[parent] = a[child];
 41         }
 42     }
 43     a[parent] = x;
 44 }
 45 
 46 /*
 47  * Implement heap sort
 48  * @param a A integer array need to sort
 49  * @param n The length of the array
 50  */
 51 void heap_sort(elementType a[], int n) {
 52     int i;
 53     /*
 54      * Build max heap
 55      */
 56     for (i = n / 2 - 1; i >= 0; i--) {
 57         percDowm(a, i, n);
 58     }
 59 
 60     /*
 61      * Swap and update heap
 62      */
 63     for (i = n - 1; i > 0; i--) {
 64         swap(&a[0], &a[i]);
 65         percDowm(a, 0, i);
 66     }
 67 }
 68 
 69 /*
 70  * Print the array to console
 71  * @param a A integer array need to sort
 72  * @param n The length of the array
 73  */
 74 void printArray(int a[], int n) {
 75     int i;
 76     for (i = 0; i < n; i++) {
 77         if (i == n - 1) {
 78             printf("%d", a[i]);
 79         } else {
 80             printf("%d ", a[i]);
 81         }
 82     }
 83     printf("\n");
 84 }
 85 
 86 /*
 87  * Get input data from command
 88  */
 89 void getInputData(elementType *a, int n) {
 90     int i;
 91     elementType x;
 92     for (i = 0; i < n; i++) {
 93         scanf("%d", &x);
 94         a[i] = x;
 95     }
 96 }
 97 
 98 int main() {
 99     int a[MAX_LENGTH];
100     int n;
101     scanf("%d", &n);
102     getInputData(a, n);
103     heap_sort(a, n);
104     printArray(a, n);
105     return 0;
106 }

Heap_Sort

 

365体育官网 24365体育官网 25

  1 /*
  2  * mergeSort.c
  3  *
  4  *  Created on: 2017年5月18日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 #define  MAX_LENGTH 100000
 11 
 12 typedef int elementType;
 13 
 14 /*
 15  * Swap two integer number value
 16  */
 17 void swap(elementType *a, elementType *b) {
 18     int temp = *b;
 19     *b = *a;
 20     *a = temp;
 21 }
 22 
 23 /*
 24  * Merge sub-sequence to original array.
 25  * @param a original <code>elementType</code> array to store the elements
 26  * @param tmpA temporary  <code>elementType</code> array to store the temporary elements
 27  * @param l The start index of left sub-sequence
 28  * @param r The start index of left sub-sequence
 29  * @param rightEnd The end index of left sub-sequence
 30  */
 31 void merge(elementType a[], elementType tmpA[], int l, int r, int rightEnd) {
 32     /*
 33      * lefeEnd is the r-1,the sub-sequence is adjacent
 34      */
 35     int leftEnd = r - 1;
 36     /*
 37      * tmp is the counter of the <code>tmpA</code>
 38      * we should let <code>tmpA</code> index corresponding original array
 39      */
 40     int tmp = l;
 41     /*
 42      * Record the quantity of the all elements
 43      */
 44     int numElements = rightEnd - l + 1;
 45     int i;
 46     while (l <= leftEnd && r <= rightEnd) {
 47         if (a[l] <= a[r]) {
 48             tmpA[tmp++] = a[l++];
 49         } else {
 50             tmpA[tmp++] = a[r++];
 51         }
 52     }
 53     while (l <= leftEnd) {
 54         tmpA[tmp++] = a[l++];
 55     }
 56     while (r <= rightEnd) {
 57         tmpA[tmp++] = a[r++];
 58     }
 59 
 60     /*
 61      * Put <code>tmpA</code> elements into the original array
 62      */
 63     for (i = 0; i < numElements; i++, rightEnd--) {
 64         a[rightEnd] = tmpA[rightEnd];
 65     }
 66 }
 67 
 68 /*
 69  * Implement the merge sort
 70  * @param a original <code>elementType</code> array to store the elements
 71  * @param tmpA temporary  <code>elementType</code> array to store the temporary elements
 72  * @param l The start index of the array which need to sort
 73  * @param rightEnd The end index of the array which need to sort
 74  */
 75 void mergetSortRecursive(elementType a[], elementType tmpA[], int l,
 76         int rightEnd) {
 77     int center;
 78     if (l < rightEnd) {
 79         center = (l + rightEnd) / 2;
 80         mergetSortRecursive(a, tmpA, l, center);
 81         mergetSortRecursive(a, tmpA, center + 1, rightEnd);
 82         merge(a, tmpA, l, center + 1, rightEnd);
 83     }
 84 }
 85 
 86 /*
 87  * Implement merge sort
 88  * @param a A integer array need to sort
 89  * @param n The length of the array
 90  */
 91 void merger_sortRecursive(elementType a[], int n) {
 92     elementType *tmpA;
 93     tmpA = malloc(n * sizeof(elementType));
 94     if (tmpA != NULL) {
 95         mergetSortRecursive(a, tmpA, 0, n - 1);
 96         free(tmpA);
 97     } else {
 98         printf("no enough space to apply for temporary array");
 99     }
100 }
101 
102 /*
103  *merge ordered sub-sequence
104  * @param a original <code>elementType</code> array to store the elements
105  * @param tmpA temporary  <code>elementType</code> array to store the temporary elements
106  * @param n The length of the a
107  * @param the ordered current sub-sequence length
108  */
109 void mergerPass(elementType a[], elementType tmpA[], int n, int lenth) {
110     int i, j;
111     /*
112      * The loop will stop when meet the last two ordered sub-sequence
113      * The rest may be two sub-sequence of one sub-sequence
114      */
115     for (i = 0; i <= n - 2 * lenth; i += lenth * 2) {
116         merge(a, tmpA, i, i + lenth, i + 2 * lenth - 1);
117     }
118     /*
119      *If the rest of is two sub-sequence
120      */
121     if (i + lenth < n) {
122         merge(a, tmpA, i, i + lenth, n - 1);
123     } else {
124         for (j = i; j < n; j++)
125             tmpA[j] = a[j];
126     }
127 }
128 
129 /*
130  * Use loop method to implement the merge sort
131  * @param a A integer array need to sort
132  * @param n The length of the array
133  */
134 void merger_SortLoop(elementType a[], int n) {
135     int length;
136     elementType *tmpA;
137     length = 1;
138     tmpA = malloc(n * sizeof(elementType));
139     if (tmpA != NULL) {
140         while (length < n) {
141             /*
142              * merge ordered sub-sequence into <code>tmpA</code>
143              */
144             mergerPass(a, tmpA, n, length);
145             length *= 2;
146             /*
147              * merge ordered sub-sequence from <code>tmpA</code> into <code>a</code>
148              */
149             mergerPass(tmpA, a, n, length);
150             length *= 2;
151         }
152         free(tmpA);
153     } else {
154         printf("no enough to apply for temporary array");
155     }
156 }
157 
158 /*
159  * Print the array to console
160  * @param a A integer array need to sort
161  * @param n The length of the array
162  */
163 void printArray(int a[], int n) {
164     int i;
165     for (i = 0; i < n; i++) {
166         if (i == n - 1) {
167             printf("%d", a[i]);
168         } else {
169             printf("%d ", a[i]);
170         }
171     }
172     printf("\n");
173 }
174 
175 /*
176  * Get input data from command
177  */
178 void getInputData(elementType *a, int n) {
179     int i;
180     elementType x;
181     for (i = 0; i < n; i++) {
182         scanf("%d", &x);
183         a[i] = x;
184     }
185 }
186 
187 int main() {
188     int a[MAX_LENGTH];
189     int n;
190     scanf("%d", &n);
191     getInputData(a, n);
192 //    merger_sortRecursive(a, n);
193     merger_SortLoop(a, n);
194     printArray(a, n);
195     return 0;
196 }

Merge_Sort

 

麻烦一天,数据结构课程的编程练习总算是跻身了前100名。付出是值得的

365体育官网 26

相关文章