c语言/c++（数据结构篇） 之 排序方法的实现实例（直接插入排序；冒泡排序；希尔排序；快速排序；简单选择排序）（6/7）_数据结构要求在一个程序中实现四种排序算法直接插入希尔冒泡快速

一、实验目的：

熟练掌握插入排序、交换排序、选择排序等排序方法。

二、实验内容

编程实现：

编写一个程序，由键盘终端输入一组无序数，将其用以下方式完成排序：

（1）直接插入排序；

（2）起泡排序；

（3）希尔排序；

（4）快速排序；

（5）简单选择排序。

并在实验结果分析与讨论出分析不同排序方式的优缺点。

程序代码：

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

using namespace std;

typedef int KeyType; 

//typedef int Elemtype;

typedef struct

{KeyType key;      //存放关键字

}Elemtype;

typedef struct

{ Elemtype data[MAX+1];   //data[0]作为监测点

 int len;

}S;

void shu_chu(S L)  //输出函数

{for (int i = 1; i <= L.len; i++)

  cout << L.data[i].key << " ";

 cout << endl;}

//直接插入排序；

void zhi_jie_cha_ru(S *L)

{int i, j;

for (i = 2; i <= L->len; i++)

 {if (L->data[i].key < L->data[i - 1].key)

{ L->data[0].key = L->data[i].key;

  for (j = i - 1; L->data[0].key < L->data[j].key; j--)

  L->data[j + 1] = L->data[j];   //记录后移

   L->data[j + 1] = L->data[0];}}}

//起泡排序

void qi_pao(S *L)

{int i, j;

 Elemtype temp;

 for(i=1;i<L->len;i++)

  for(j=1;j<=L->len-i;j++)

   if (L->data[j].key < L->data[j + 1].key)

   { temp = L->data[j + 1];

    L->data[j + 1] = L->data[j];

L->data[j] = temp;}}

//希尔排序

void Xi_er(Elemtype data[], int length, int delta)

{

 int i, j;

 for(i=1+delta;i<=length;i++)

  if (data[i].key > data[i - delta].key)

  {

   data[0] = data[i];

   for (j = i - delta; j > 0 && data[0].key > data[j].key; j -= delta)

    data[j + delta] = data[j];

   data[j + delta] = data[0];

  }

}

//快速排序

int kuai_su(Elemtype data[], int left, int right)

{

 int low, high;

 low = left; high = right;

 data[0] = data[low];

 int pivo;

 pivo = data[low].key;

 while (low < high)

 {

  while (low < high&&data[high].key >= pivo)

   high--;

  if (low < high)

   data[low] = data[high];

  while (low < high&&data[low].key <= pivo)

   low++;

  if (low < high)

   data[high] = data[low];

 }

 data[low] = data[0];

 return low;

}

void Kuai_su(S *L,int low,int high)

{

 int pivo;

 if (low < high)

 {

  pivo = kuai_su(L->data, low, high);

  Kuai_su(L, low, pivo - 1);

  Kuai_su(L, pivo + 1, high);

 }

}

//简单选择排序

void Jian_dan_xuan_ze(S *L)

{

 int i, j,k;

 Elemtype temp;

 for (i = 1; i < L->len; i++)

 {

  k = i;

  for (j = i + 1; j <= L->len; j++)   //从i开始的length-i+1个记录中选取

   if (L->data[k].key > L->data[j].key)

    k = j;

  if (k != i)

  {

   temp = L->data[k];

   L->data[k] = L->data[i];

   L->data[i] = temp;

  }

 }

}

void Xi_er(S *L, int delta[], int n)

{

 for (int i = 0; i <= n - 1; i++)

  Xi_er(L->data, L->len, i);

}

int main()

{

 int i,n,cj,A[20];

 S L;

 cout << "请你输入要排序的元素个数：\n";

 cin >> n;

 L.len = n;

  cout << "请输入想要使用的方法：\n" << endl;

  cout << "1.直接插入排序" << endl;

  cout << "2.起泡排序" << endl;

  cout << "3.希尔排序" << endl;

  cout << "4.快速排序" << endl;

  cout << "5.简单选择排序" << endl;

  cin >> cj;

printf("你选择的是第%d种方法，",cj);

printf("你现在输入%d个数开始排序\n",n);

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

 {

  cin >> L.data[i].key;

  A[i] = L.data[i].key;

 }

  switch (cj)

  {

  case 1:

  {

   zhi_jie_cha_ru(&L);

   cout << "直接插入排序结果为：\n" << endl;

   shu_chu(L);

  }break;

  case 2:

  {

qi_pao(&L);

    cout << "起泡排序排序结果为：\n" << endl;

   shu_chu(L);

  }break;

  case 3:

  {

 Xi_er(&L ,A,9); 

    cout << "希尔排序结果为：\n" << endl;

    shu_chu(L);

  }break;

  case 4:

  {

Kuai_su(&L, 1, 9);

    cout << "快速排序结果为：\n" << endl;

    shu_chu(L);

  }break;

  case 5:

  {

  Jian_dan_xuan_ze(&L);

    cout << "简单选择排序结果为：\n" << endl;

   shu_chu(L);

  }break;

}

}

运行结果及体会见（7/7）部分

分析与讨论：

1.直接插入排序

优点:具有稳定性，代码逻辑简单明了，容易编写。排序数少的时候具有优势。

缺点:比较次数不确定，当排序的数总量大的时候，排序次数多。

2.起泡排序

优点:具有稳定性 比较简单,空间复杂度较低，是稳定的:

缺点:时间花费相对较高高，效率相对较慢。

3.希尔排序

优点：运行速度快，排序次数较少。是对直接插入排序的优化，复杂度较低

缺点：具有不稳定性质，需要有经验进行排序。

4.快速排序;

优点:极快，数据移动少。

缺点:具有不稳定性，。

5.简单选择排序

优点: 是一种简单直观的排序算法，能够计算排序次数，代码容易编写。

缺点:具有不稳定性，比较次数多。