AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构课设——排序综合(C语言)

2023-09-01 84
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构课设——排序综合(C语言)

数据结构课设——排序综合(C语言)

文章目录

题目

利用随机函数产生N个随机整数（20000以上）,对这些数进行多种方法进行排序。

要求：

  1. 至少采用四种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
  2. 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比，），找出其中两种较快的方法。

本程序中用到了6种排序方法。

随机数的生成

srand((unsigned)time(NULL));

srand用来初始化随机种子，会提供一个种子，这个种子会对应一个随机数。

为了防止随机数每次重复，这里使用系统时间来作为随机种子。

1.插入排序

步骤

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取下一个元素temp,从已排序的元素序列从后往前遍历
  3. 如果该元素大于temp,则将该元素移到下一位
  4. 重复步骤3，直到找到已排序元素中小于等于temp的元素
  5. temp插入到元素的后面，如果已排序的元素都大于temp，则将temp插入到下标为0的位置
  6. 重复步骤2~5

动图演示如下:91fd8728272ab77cc5ca887341bb3783.gif

void insertSort()
{
    for (int i = 1; i < CAPACITY; i++)
  {
    int temp = array[i];
    int j = i - 1;
    while (j >= 0)
    {
      //说明前面已经有序了
      if (array[j] <= temp)
      {
        break;
      }
      //移动j的值到j+1
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = temp;
  }
}

时间复杂度:最坏情况:O(image.png),最好情况 O(N)

空间复杂度:O(1)

稳定性:稳定

2.希尔排序

希尔排序又称缩小增量法

步骤

  1. 先定义一下分组个数gap
  2. 把整个数组分成gap个组，每个组里有CAPACITY/gap个元素
  3. 把每个小组分别用插入方式排序
  4. 逐渐缩小这个gap，直到gap=1时，全部排序完成
  5. 85d482479380a6218e26402427cf5421.gif
  6. ce72a2a06e7e254acf4b592a6defb29d.png
void shellSort()
{
  int gap = CAPACITY / 2;
  while (gap > 0)
  {
    shell( gap);
    gap /= 2;
  }
}
//核心代码
void shell( int gap)
{
  for (int i = gap; i < CAPACITY; i++) 
  {
    int temp = array[i];
    int j = i - gap;
    while (j >= 0)
    {
      if (array[j] <= temp) 
      {
        break;
      }
      array[j + gap] = array[j];
      j -= gap;
    }
    array[j + gap] = temp;
  }
}

时间复杂度:O(image.png

空间复杂度:O(1)

稳定性:不稳定

3.冒泡排序

左边大于右边交换一趟排下来最大的在右边e69c865e72338b69c84dc88684c4c428.gif

void bubbleSort()
{
  for (int i = 0; i < CAPACITY - 1; i++) {
    int set = 0;
    for (int j = 0; j < CAPACITY - 1 - i; j++) 
    {
      if (array[j] > array[j + 1]) 
      {
        swap(j, j + 1);
        set = 1;
      }
    }
    if (set==0)
    {
      break;
    }
  }
}
void swap(int left, int right)
{
  int temp = array[left];
  array[left] = array[right];
  array[right] = temp;
}

image.png

4.快速排序

挖坑法找基准


  1. left下标的值当做默认的基准值，这时left的位置就空出来了
  2. right向左移动，找到比基准值小的值，放到left的位置
  3. left向右移动，找到比基准值大的值，放到right的位置
  4. 当left 与right相遇时，把之前记录的基准值放在相遇的下标
  5. 返回相遇点下标，这就是基准的下标944d6aec7751150fef18c25e26fc6ae6.gif
//快速排序
void quickSort()
{
  const int N = 1e2;
    start = clock();
  quickSortProcess(0, CAPACITY - 1);
  end = clock();
  printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
//核心代码
void quickSortProcess(int left, int right)
{
  if (left>=right)
  {
    return;
  }
  //找基准
  int pivot= partitionHole(left, right);
  quickSortProcess(left, pivot);
  quickSortProcess( pivot+1,right);
}
int partitionHole(int left, int right)
{
  int pivotValue = array[left];
  while (left < right) 
  {
    while (right > left && array[right] >= pivotValue) 
    {
      right--;
    }
    array[left] = array[right];
    while (left < right && array[left] <= pivotValue) 
    {
      left++;
    }
    array[right] = array[left];
  }
  array[left] = pivotValue;
  return left;
}

image.png

5.选择排序

步骤


定义数组边界，left=0,right=CAPACITY-1

定义i用来遍历

定义最小值下标minIndex=left,maxIndex=left

在i遍历的过程中，找到比最小值小的元素更新minIndex,找到比最大值大的元素更新maxIndex

一轮遍历完成后，left与minIndex交换，right与maxIndex交换

循环终止条件是left<rigth

fa8a542ef872353b275847bf672e9c04.gif

//选择排序
void selectSort()
{
  int left = 0;
  int right = CAPACITY - 1;
  while (left < right) 
  {
    int minIndex = left;
    int maxIndex = left;
    //找最大值和最小值
    for (int i = left + 1; i <= right; i++) 
    {
      if (array[i] < array[minIndex]) 
      {
        minIndex = i;
      }
      if (array[i] > array[maxIndex]) 
      {
        maxIndex = i;
      }
    }
    if (left != minIndex) 
    {
      swap(left, minIndex);
    }
    if (left == maxIndex) 
    {
      minIndex = maxIndex;
    }
    if (right != maxIndex) 
    {
      swap(right, maxIndex);
    }
    left++;
    right--;
  }
}

image.png

6.归并排序

步骤

  1. 把大数组分解成若干个小数组
  1. 把小数组做归并操作，并在归并的过程中完成排序


    1. 在归并的过程中，需要用到一个临时数组来存储排序好的数据，那么这个数组的容量为 right-left+1
    2. 确定每个小数组的开始与结束下标
    1. 合并两个数组，合并的方法可以参考合并有序数组的过程
    1. 两个数组都不为空的情况下，比当前位置元素的大小，小的那一个直接加入到临时数组里
    2. 如果两个数组的元素个数不一样多，那么就要处理有剩余元素的数组，直接把剩余元素追加到临时数组里
    1. 把临时数组中排序好的元素，覆盖到原数组对应的下标

    10d7b5dc10b024bbec57af957eb61331.png

    //归并排序
void mergeSort()
{
    mergeSortProcessor( 0, CAPACITY - 1);
}
void mergeSortProcessor(int left, int right)
{
    //1、终止条件
    if (left >= right) {
        return;
    }
    //2、找中间下标
    int mid = (left + right) / 2;
    //3、分解左右区段
    mergeSortProcessor( left, mid);
    mergeSortProcessor( mid + 1, right);
    //4、合并
    marge( left, mid, right);
}
void marge(int left, int mid, int right)
{
    //1、创建临时数组
    //int n = (right - left + 1);
    int *temp=(int*)malloc((right - left + 1)*sizeof(int));
    int index = 0;
    //2、确定每个小数组的下标
    int start1 = left;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = right;
    //3、合并
    while (start1 <= end1 && start2 <= end2) {
        if (array[start1] < array[start2]) {
            temp[index++] = array[start1++];
        }
        else {
            temp[index++] = array[start2++];
        }
    }
    //剩余元素添加到temp中
    while (start1 <= end1) {
        temp[index++] = array[start1++];
    }
    while (start2 <= end2) {
        temp[index++] = array[start2++];
    }
    //4、temp写到原数组中
    for (int i = 0; i < index; i++) {
        array[i + left] = temp[i];
    }
    free(temp);
    temp = NULL;
}

    image.png

    完整代码

    sort.h

    #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define CAPACITY 20000
int array[CAPACITY];
clock_t start, end;
void initArray();
void save(char* name1);
void dispaly();
void swap(int i, int minIndex);
//插入排序
void insertSort();
//希尔排序
void shellSort();
void shell(int gap);
//冒泡排序
void bubbleSort();
//快速排序
void quickSort();
void quickSortProcess(int left, int right);
int partitionHole(int left, int right);
//选择排序
void selectSort();
//归并排序
void mergeSort();
void mergeSortProcessor(int left, int right);
void marge(int left, int mid, int right);

    sort.c

    #include"sort.h"
void initArray()
{
  srand((unsigned)time(NULL));
  for (int i = 0; i < CAPACITY; i++)
  {
    array[i] = rand();
  }
}
void save(char* name1)
{
  FILE* fp;
  char* name2 = ".txt";
  char* name = (char*)malloc(strlen(name1) + strlen(name2));
  strcpy(name, name1);
  strcat(name, name2);
  fp = fopen(name, "w");
  int count = 0;
  for (int i = 0; i < CAPACITY; i++)
  {
    fprintf(fp, "%6d", array[i]);
    count++;
    if (count%100==0)
    {
      fprintf(fp, "\n");
    }
  }
  fclose(fp);
}
void dispaly()
{
  int count = 0;
  for (int i = 0; i < CAPACITY; i++)
  {
    printf("%6d", array[i]);
    count++;
    if (count % 20 == 0)
    {
      printf("\n");
    }
  }
  printf("\n");
}
//插入排序
void insertSort()
{
  const int N = 1e2;
  start = clock();
  for (int i = 1; i < CAPACITY; i++)
  {
    int temp = array[i];
    int j = i - 1;
    while (j >= 0)
    {
      //说明前面已经有序了
      if (array[j] <= temp)
      {
        break;
      }
      //移动j的值到j+1
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = temp;
  }
  end = clock();
  printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
//希尔排序
void shellSort()
{
  const int N = 1e2;
  start = clock();
  int gap = CAPACITY / 2;
  while (gap > 0)
  {
    shell( gap);
    gap /= 2;
  }
  end = clock();
  printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
void shell( int gap)
{
  for (int i = gap; i < CAPACITY; i++) 
  {
    int temp = array[i];
    int j = i - gap;
    while (j >= 0)
    {
      if (array[j] <= temp) 
      {
        break;
      }
      array[j + gap] = array[j];
      j -= gap;
    }
    array[j + gap] = temp;
  }
}
void swap(int left, int right)
{
  int temp = array[left];
  array[left] = array[right];
  array[right] = temp;
}
//冒泡排序
void bubbleSort()
{
  const int N = 1e2;
  start = clock();
  for (int i = 0; i < CAPACITY - 1; i++) {
    int set = 0;
    for (int j = 0; j < CAPACITY - 1 - i; j++) 
    {
      if (array[j] > array[j + 1]) 
      {
        swap(j, j + 1);
        set = 1;
      }
    }
    if (set==0)
    {
      break;
    }
  }
  end = clock();
  printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
//快速排序
void quickSort()
{
  const int N = 1e2;
    start = clock();
  quickSortProcess(0, CAPACITY - 1);
  end = clock();
  printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
//核心代码
void quickSortProcess(int left, int right)
{
  if (left>=right)
  {
    return;
  }
  //找基准
  int pivot= partitionHole(left, right);
  quickSortProcess(left, pivot);
  quickSortProcess( pivot+1,right);
}
int partitionHole(int left, int right)
{
  int pivotValue = array[left];
  while (left < right) 
  {
    while (right > left && array[right] >= pivotValue) 
    {
      right--;
    }
    array[left] = array[right];
    while (left < right && array[left] <= pivotValue) 
    {
      left++;
    }
    array[right] = array[left];
  }
  array[left] = pivotValue;
  return left;
}
//选择排序
void selectSort()
{
  const int N = 1e2;
    start = clock();
  int left = 0;
  int right = CAPACITY - 1;
  while (left < right) 
  {
    int minIndex = left;
    int maxIndex = left;
    //找最大值和最小值
    for (int i = left + 1; i <= right; i++) 
    {
      if (array[i] < array[minIndex]) 
      {
        minIndex = i;
      }
      if (array[i] > array[maxIndex]) 
      {
        maxIndex = i;
      }
    }
    if (left != minIndex) 
    {
      swap(left, minIndex);
    }
    if (left == maxIndex) 
    {
      minIndex = maxIndex;
    }
    if (right != maxIndex) 
    {
      swap(right, maxIndex);
    }
    left++;
    right--;
  }
  end = clock();
    printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
//归并排序
void mergeSort()
{
    const int N = 1e2;
  start = clock();
  mergeSortProcessor( 0, CAPACITY - 1);
  end = clock();
    printf("time: %f s\n", ((double)(end - start)) / CLOCKS_PER_SEC / N);
}
void mergeSortProcessor(int left, int right)
{
  //1、终止条件
  if (left >= right) {
    return;
  }
  //2、找中间下标
  int mid = (left + right) / 2;
  //3、分解左右区段
  mergeSortProcessor( left, mid);
  mergeSortProcessor( mid + 1, right);
  //4、合并
  marge( left, mid, right);
}
void marge(int left, int mid, int right)
{
  //1、创建临时数组
  //int n = (right - left + 1);
  int *temp=(int*)malloc((right - left + 1)*sizeof(int));
  int index = 0;
  //2、确定每个小数组的下标
  int start1 = left;
  int end1 = mid;
  int start2 = mid + 1;
  int end2 = right;
  //3、合并
  while (start1 <= end1 && start2 <= end2) {
    if (array[start1] < array[start2]) {
      temp[index++] = array[start1++];
    }
    else {
      temp[index++] = array[start2++];
    }
  }
  //剩余元素添加到temp中
  while (start1 <= end1) {
    temp[index++] = array[start1++];
  }
  while (start2 <= end2) {
    temp[index++] = array[start2++];
  }
  //4、temp写到原数组中
  for (int i = 0; i < index; i++) {
    array[i + left] = temp[i];
  }
  free(temp);
  temp = NULL;
}

    main.c

    #include"sort.h"
void menu()
{
  printf("+===================================+\n");
  printf("+        欢迎使用综合排序系统       +\n");
  printf("+            1.插入排序             +\n");
  printf("+            2.希尔排序             +\n");
  printf("+            3.冒泡排序             +\n");
  printf("+            4.快速排序             +\n");
  printf("+            5.选择排序             +\n");
  printf("+            6.归并排序             +\n");
  printf("+            0.退出程序             +\n");
  printf("+===================================+\n");
}
void setting()
{
  system("color 0b");
}
int main()
{
  setting();
  while (1)
  {
    int select;
    //生成随机数组
    initArray();
    //dispaly();
    menu();
    printf("请选择需要进行的操作:");
    scanf("%d", &select);
    switch (select)
    {
    case 1:
      insertSort();
      save("插入排序");
      system("pause");
      system("cls");
      break;
    case 2:
      shellSort();
      save("希尔排序");
      system("pause");
      system("cls");
      break;
    case 3:
      bubbleSort();
      save("冒泡排序");
      system("pause");
      system("cls");
      break;
    case 4:
      quickSort();
      save("快速排序");
      //dispaly();
      system("pause");
      system("cls");
      break;
    case 5:
      selectSort();
      save("选择排序");
      system("pause");
      system("cls");
      break;
    case 6:
      mergeSort();
      save("归并排序");
      system("pause");
      system("cls");
      break;
    case 0:
      printf("拜拜,欢迎下次使用.....\n");
      return 0;
      break;
    default:
      printf("选择无效,请重新选择!!!\n");
      system("pause");
      system("cls");
      break;
    }
  }
}
    文章标签：
    C语言
    存储
    关键词：
    排序C语言
    数据结构c语言
    数据结构排序
    数据结构课设
    小王90703
    目录
    相关文章
    ephemerals__
    |
    20天前
    |
    C语言
    【数据结构】栈和队列（c语言实现）（附源码）
    本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
    ephemerals__
    103 9
    ephemerals__
    |
    19天前
    |
    存储 搜索推荐 算法
    【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
    本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
    ephemerals__
    60 16
    ephemerals__
    |
    15天前
    |
    搜索推荐 算法 C语言
    【排序算法】八大排序（上）（c语言实现）（附源码）
    本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
    ephemerals__
    61 8
    ephemerals__
    |
    15天前
    |
    搜索推荐 算法 C语言
    【排序算法】八大排序（下）（c语言实现）（附源码）
    本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
    ephemerals__
    51 7
    ephemerals__
    |
    19天前
    |
    C语言
    【数据结构】二叉树（c语言）（附源码）
    本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
    ephemerals__
    70 8
    ephemerals__
    |
    22天前
    |
    存储 C语言
    【数据结构】手把手教你单链表（c语言）（附源码）
    本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
    ephemerals__
    49 4
    ephemerals__
    |
    23天前
    |
    存储 C语言
    【数据结构】顺序表（c语言实现）（附源码）
    本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
    ephemerals__
    56 3
    可惜已不在
    |
    1月前
    |
    算法 C语言
    【C语言】排序查找
    【C语言】排序查找
    可惜已不在
    17 2
    java冯坚持
    |
    1月前
    |
    算法 搜索推荐 Java
    数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
    基数排序是一种稳定的排序算法，通过将数字按位数切割并分配到不同的桶中，以空间换时间的方式实现快速排序，但占用内存较大，不适合含有负数的数组。
    java冯坚持
    24 0
    数据结构与算法学习十三：基数排序，以空间换时间的稳定式排序,速度很快。
    GuGuStudy
    |
    1月前
    |
    存储 搜索推荐 算法
    【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
    【用Java学习数据结构系列】七大排序要悄咪咪的学（直接插入，希尔，归并，选择，堆排，冒泡，快排）以及计数排序（非比较排序）
    GuGuStudy
    24 1