精华内容
下载资源
问答
  • 数据结构课程设计报告 数据结构课程设计报告 几种排序算法的演示 几种排序算法的演示 时间2010-1-14 时间2010-1-14 一 需求分析 一 需求分析 运行环境 运行环境 Microsoft Visual Studio 2005 Microsoft Visual ...
  • Python数据结构与算法(几种排序数据结构与算法(Python) 冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。...
  • 以下我们将介绍几种常见的排序,几种排序算法的时间复杂度及稳定性如下: 1、冒泡排序 冒泡排序的效率很低,但是算法实现起来很简单,因此很适合作为研究排序的入门算法。 基本思想 对当前还未排好序的...

    所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。

    以下我们将介绍几种常见的排序,几种常见的排序算法的时间复杂度及稳定性如下:

    在这里插入图片描述
    下面介绍几种排序的原理及java实现:

    1、冒泡排序

    冒泡排序(Bubble Sort)的效率很低,但是算法实现起来很简单,因此很适合作为研究排序的入门算法。

    • 基本思想
      对当前还未排好序的范围内的全部数,自左向右对相邻的俩个数依次进行比较和调整,让较大的数下沉,较小的数往上冒。即:每当俩相邻的数比较后发现他们的排序与排序的要求相反时,就将他们交换。每次遍历都可确定一个最大值放到待排数组的末尾,下次遍历,对该最大值以及它之后的元素不再排序。

    • java代码实现

    package com.example.demo.sort;
    
    public class BubbleSort {
       public static void bubbleSort(int [] arr){
           int counter = 1;
           //外层循环:每循环一次就确定了一个相对最大元素
           for (int i = 0; i < arr.length - 1; i++) {
               //内层循环:有i个元素已经排好,根据i确定本次的比较次数
               for (int j = 0; j < arr.length -i -1; j++) {
                   //如果前一位大于后一位,交换位置
                   if (arr[j] > arr[j+1]){
                       int temp = arr[j];
                       arr[j] = arr[j + 1];
                       arr[j + 1] = temp;
                   }
               }
               System.out.print("\n" + "第"+ counter +"轮排序结果:");
               for (int k = 0; k < arr.length; k++) {
                   System.out.print(arr[k] + " ");
               }
               counter++;
           }
       }
    
       public static void main(String args[]) {
           int arr[] = {23, 14, 57, 22, 8, 5};
           //打印排序前的数组
           System.out.println("排序前");
           for (int i = 0; i < arr.length; i++) {
               System.out.print(arr[i] + " ");
           }
           bubbleSort(arr);
           //打印排序后的数组
           System.out.println("\n" + "排序后");
           for (int i = 0; i < arr.length; i++) {
               System.out.print(arr[i] + " ");
           }
       }
    }
    
    

    代码中有注释,不懂得可以看注释。运行结果如下:
    在这里插入图片描述
    可以看出每一趟的排序都把较大的那一个数冒出来了放在数组最后。

    2、选择排序

    • 基本思想
      选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

    • java代码实现

    package com.example.demo.sort;
    
    public class SelectSort {
      public static void selectSort(int [] arr ){
          int minIndex ; //存储最小元素的下标
          int counter = 1;
          for (int i = 0; i < arr.length - 1; i++) {
              minIndex = i ;
              for (int j = i; j <= arr.length - 1; j++){
                  if (arr[j] <arr[minIndex]){
                      minIndex = j;
                  }
              }
              if (minIndex != i){
                  int temp = arr[i];
                  arr[i] = arr[minIndex];
                  arr[minIndex] = temp;
              }
              System.out.print("\n" + "第"+ counter +"轮排序结果:");
              for (int k = 0; k < arr.length; k++) {
                  System.out.print(arr[k] + " ");
              }
              counter++;
          }
    
      }
    
      public static void main(String args[]){
          int arr[] = {56, 18, 35, 4, 15, 47};
          //打印排序前的数组
          System.out.println("排序前");
          for (int i = 0; i < arr.length; i++) {
              System.out.print(arr[i] + " ");
          }
          selectSort(arr);
          //打印排序后的数组
          System.out.println("\n" + "排序后");
          for (int i = 0; i < arr.length; i++) {
              System.out.print(arr[i] + " ");
          }
      }
    
    }
    

    运行结果如下:
    在这里插入图片描述
    可以看到它每轮排序都会在待排序的数中找到最小的,然后和待排序的第一个数交换位置,以此类推。

    3、插入排序

    • 基本思想
      插入排序(Insert Sort)是从整个待排序列中选出一个元素插入到已经有序的子序列中去,得到一个有序的、元素加一的子序列,直到整个序列的待插入元素为0,则整个序列全部有序。

    • java代码实现

    package com.example.demo.sort;
    
    public class InsertSort {
      public static void insertSort(int [] arr){
          int counter = 1;
          //要对该待排序列的每一个元素都和前面的已排好序的序列进行插入,对序列进行遍历
          for (int i = 0; i < arr.length; i++){
              //第二层循环主要用于对已排好序的序列进行扫描,和要插入进来的数据进行逐一比较,然后决定插入到哪里
              for (int j = 0; j < i; j++){
                  if (arr[j] > arr[i]){
                      int temp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = temp;
                  }
              }
              System.out.print("\n" + "第"+ counter +"轮排序结果:");
              for (int k = 0; k < arr.length; k++) {
                  System.out.print(arr[k] + " ");
              }
              counter++;
          }
      }
    
      public static void main(String args[]){
          int arr[] = {56, 18, 35, 4, 15, 47};
          //打印排序前的数组
          System.out.println("排序前");
          for (int i = 0; i < arr.length; i++) {
              System.out.print(arr[i] + " ");
          }
          insertSort(arr);
          //打印排序后的数组
          System.out.println("\n" + "排序后");
          for (int i = 0; i < arr.length; i++) {
              System.out.print(arr[i] + " ");
          }
      }
    }
    

    运行结果如下:
    在这里插入图片描述
    可以看出,它确实是将数一个个插入到一个有序数组中的。

    4、归并排序

    • 基本思想
      归并排序(MERGE-SORT)是将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    • java代码实现

    • 两路归并排序算法思路
      ①把 n 个记录看成 n 个长度为1的有序子表;
      ②进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表;
      ③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。

    package com.example.demo.sort;
    
    /**
    * 递归实现
    */
    public class MergeSort {
    
      static int number=0;
    
      private static void printArray(String pre,int[] a) {
          System.out.print(pre+"\n");
          for(int i=0;i<a.length;i++)
              System.out.print(a[i]+"\t");
          System.out.println();
      }
    
      private static void mergeSort(int[] a) {
          // TODO Auto-generated method stub
          System.out.println("开始排序");
          sort(a, 0, a.length - 1);
      }
    
      private static void sort(int[] a, int left, int right) {
          if(left>=right)
              return;
    
          int mid = (left + right) / 2;
          //二路归并排序里面有两个Sort,多路归并排序里面写多个Sort就可以了
          sort(a, left, mid);
          sort(a, mid + 1, right);
          merge(a, left, mid, right);
    
      }
    
      private static void merge(int[] a, int left, int mid, int right) {
          int[] tmp = new int[a.length];
          int r1 = mid + 1;
          int tIndex = left;
          int cIndex=left;
          // 逐个归并
          while(left <=mid && r1 <= right) {
              if (a[left] <= a[r1])
                  tmp[tIndex++] = a[left++];
              else
                  tmp[tIndex++] = a[r1++];
          }
          // 将左边剩余的归并
          while (left <=mid) {
              tmp[tIndex++] = a[left++];
          }
          // 将右边剩余的归并
          while ( r1 <= right ) {
              tmp[tIndex++] = a[r1++];
          }
    
          System.out.println("第"+(++number)+"趟排序:\t");
          // TODO Auto-generated method stub
          //从临时数组拷贝到原数组
          while(cIndex<=right){
              a[cIndex]=tmp[cIndex];
              //输出中间归并排序结果
              System.out.print(a[cIndex]+"\t");
              cIndex++;
          }
          System.out.println();
      }
    
      public static void main(String[] args) {
          int[] a = {56, 18, 35, 4, 15, 47};
          printArray("排序前:",a);
          mergeSort(a);
          printArray("排序后:",a);
      }
    }
    

    运行结果如下:
    在这里插入图片描述

    想要源码的同学们可以在评论区留言,小姐姐我双手奉上~

    展开全文
  • 几种常见排序算法的实现与性能分析数据结构课程设.doc
  • 数据结构常见几种排序算法

    千次阅读 多人点赞 2018-08-27 15:52:20
    数据结构常见几种排序算法 快速排序 目录 数据结构常见几种排序算法 快速排序 插入排序 希尔排序 归并排序 堆排序 选择排序 冒泡排序 基数排序 快速排序 基本思想: 基准分割法  a) 通过一趟...

     

     

    数据结构中常见的几种排序算法

    快速排序

    目录

    数据结构中常见的几种排序算法

    快速排序

    插入排序

    希尔排序

    归并排序

    堆排序

    选择排序

    冒泡排序

    基数排序


    快速排序

    基本思想: 基准分割法

     a) 通过一趟排序将要排序的数据分割成独立的两部分其中一部分所有的数据要比另外的一部分数据都要小

     b) 按照此方法对这两部分数据进行快速排序

     案例:3 6 5 8 4 2 1 9

       快排过程:3 6 5 8 4 2 1 9 => 2 1 |3| 6 5 8 4 9 => 1 |2| |3| 5 4 |6| 8 9 => 1 |2| |3| 4 |5| |6| |8| 9 => 1 2 3 4 5 6 8 9 

       改进的快排:随机快排

      思想:若对数组9 8 7 6 5 4 3 2 1进行快排,每次选取第一个元素作为基准元素,分组将很不均衡,这种极端情况将 导致时间复杂度和简单排序一样。为避免这样的极端情况,选取一个随机数作为基准元素

    步骤:

    a) 从数列中选一个元素 称“基准”

    b) 重新排列数列,所有元素比基准小的摆放在基准的前面,所有比基准大的元 `` 素摆放在基准后面,这个分区退出之后 基准就处于数列的中间位置,称为分区操作,

    c) 递归的把小于基准值元素的子数列和大于基准值元素的子数列排序

     

    //快速排序
    int QuickSort(int a[], int left,int right)
    {
    	int i = left, j = right, x = a[left];
    	while (i < j)
    	{
    		while (i<j && a[j]>x)
    			j--;
    		if (i < j)
    			a[i++] = a[j];
    
    
    	
    		while (i < j && a[i] < x)
    			i++;
    		if (i < j)
    			a[j--] = a[i];
    	a[i] = x;
    	QuickSort(a, left, right - 1);
    	QuickSort(a, left + 1, right);
    	}
    return 0;
    }

    插入排序

    基本原理 :

    构建有序序列,对于未排序数据 在已经排序序列中从后往前扫描,找到相应的位置进行插入,在从后向前的扫描过程中需要反复把已经排序的元素逐步向后挪位,为最新元素插入提供空间。

    步骤:

    a 从第一个元素开始,该元素可以认为已经被排序

    b 取出下一个元素 在已经排序的元素序列中从后向前扫描

    c 如果该元素(已排序)大于新元素,将该元素移到下一位置

    d 重复c步骤直到找到已排序的元素小于或者等于新元素的位置

    e 将新元素插入到该位置

    f 重复步骤b

    //插入排序
    void InsertSort(int a[], int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		int get = a[i];
    		int j = i - 1;
    		while (j>=0 && a[j]>get)
    		{
    			a[j + 1] = a[j];
    			j--;
    		}
    		a[j + 1] = get;
    	}
    }
    
    

    希尔排序

    增量排序,又叫递减增量排序,也是直接插入排序算法的一种高效的改进版本 是不稳定的

    基本思想 :

    将元素进行同余分组,比如元素个数有8个,若将其分为d1=4组,即每一个元素的下标进行模3运算,下标{0,4}模4余数都为0为一组,{1,5}余1 为一组,{2,6}余2为一组,{3,7}余3为一组,当然这只是一种逻辑上的划分,并不是物理上对其进行切分。然后在各组内进行直接插入排序,排序完再对其进行分组,一般取d(i+1) = ⌊d(i)/2⌋,此时的话d2=⌊d1/2⌋= 2组,就这样一直分组排序到di = 1并插入排序结束

     

     

    //希尔排序  高效的插入排序
    void ShellSort(int a[], int size)
    {
    	int h = 0;
    	while (h <= size)
    	{
    		h = h * 3 + 1;
    	}
    
    	while (h >= 1)
    	{	
    		for (int i = h; i < size; i++)
    		{
    			int j = i - h;
    			int get = a[i];
    			while (j >= 0 && a[j]>get)
    			{
    				a[j + h] = a[j];
    				j = j - h;
    			}
    			a[j + h] = get;
    		}
    		h = (h - 1) / 3;
    	}
    }

    归并排序

    采用分治法()

    基本思想:

    1)将已经有序的子序列合并,得到完全有序的序列,

    2)先使每个子序列有序,再使子序列段间有序

    3)若将两个有序表合并成一个有序表称为二路归并

     

    步骤:

    a 申请空间,让他大小为两个已经排序的序列之和,

    该空间用来存放合并后的序列

    b 设定两个指针,最初位置分别为两个已经排序序列起始位置

    c 比较两个指针所指向的元素,选择相对较小的放入合并空间,并移动

    指针到下一个位置

    d 重复步骤c 知道某个指针达到序列尾

    e 将另一个序列剩下的所有元素直接复制到合并序列尾。

    //归并排序
    void Merge(int a[], int left, int mid,int right)
    {
    	int size = right - left + 1;
    	int *temp = (int *)malloc(size*sizeof(int));
    	int i = left;
    	int j = mid + 1;
    	int index = 0;
    	while (i <= mid && j <= right)
    	{
    		temp[index++] = a[i] < a[j] ? a[i++] : a[j++];
    	}
    	while (i <= mid)
    	{
    		temp[index++] = a[i++];
    	}
    	while (j <= right)
    	{
    		temp[index++] = a[j++];
    	}
    	for (int k = 0; k < size; k++)
    	{
    		a[left++] = temp[k];
    	}
    }
    
    
    
    void MergeSort(int a[], int left, int right)
    {
    	if (left == right) return;
    	int mid = left + ((right - left) >> 1);
    	MergeSort(a, left, mid);
    	MergeSort(a, mid + 1, right);
    	Merge(a, left, mid, right);
    }

    堆排序

    利用堆 这种数据结构所设计的一种排序算法,也是选择排序的一种。

    a 可以利用数组的特点快速定位指定索引的元素

    b 堆分为大堆小堆 是完全二叉树

    大堆 要求每个节点的值都不大于其父节点的值即a[parent]>=a[i]

    在数组的非降序排序中,需要使用的就是大堆

    大堆中最大值肯定是在 堆顶的

    步骤:a 首先将序列构建称为大顶堆;

    (这样满足了大顶堆那条性质:位于根节点的元素一定是当前序列的最大值)

    b 取出当前大顶堆的根节点,将其与序列末尾元素进行交换;

    (此时:序列末尾的元素为已排序的最大值;由于交换了元素,当前位于根节点的堆并不一定满足大顶堆的性质)

    c 重复a.b步骤,直至堆中只有1个元素为止

     

    //堆排序
    void HeapModify(int a[], int i, int size)//向下调整
    {
    	int left_child = i * 2 + 1;//左孩子索引
    	int right_child = i * 2 + 2;//右孩子索引
    	int max = i;//选出当前节点与其左右孩子三者中最大值
    	if (left_child<size && a[left_child]>a[max])
    		max = left_child;
    	if (right_child<size && a[right_child]>a[max])
    		max = right_child;
    
    	if (max != i)
    	{
    		swap(a, i, max);//将当前节点与其最大子节点进行交换
    		HeapModify(a, max, size);// 递归调用 继续从当前节点向下进行堆调整
    	}
    }
    //建堆
    int BuildHeap(int a[], int size)
    {
    	int heap_size = size;
    	for (int i = (heap_size >> 1) - 1; i >= 0; --i)
    	{
    		HeapModify(a, i, heap_size);
    	}
    	return heap_size;
    }
    void HeapSort(int a[], int size)
    {
    	int heap_size = BuildHeap(a, size);//建大堆
    	while (heap_size > 1)
    	{
    		swap(a, 0, --heap_size);
    		HeapModify(a, 0, heap_size);//从新的堆顶元素开始向下调整,时间复杂度为O(lgn)
    	}
    }

    选择排序

    排序原理:

    a 首先在未排序序列中找到最小元素,存放到排序序列的起始位置,

    b 再从未排序元素中继续寻找最小元素,然后放到排序序列尾

    c 一次类推 直到所有元素都排序完毕

     

    //选择排序
    void SelectSort(int a[], int size)
    {
    	for (int i = 0; i < size-1; ++i)
    	{
    		int min = i;
    		for (int j = i + 1; j < size - 1; ++j)
    		{
    			if (a[j] < a[min])
    				min = j;
    		}
    		if (min != i)
    			swap(a, min, i);
    	}
    }

    冒泡排序

    排序原理:

    a)重复地走访过要排序的数列,一次比较两个元素,

    如果他们顺序错误就把他们交换过来

    b)走访数列的工作就是重复地进行 直到没有再需要交换,

    也就是说该数列已经排序完成

    c) 这个算法就是因为越小的元素会经由交换慢慢浮到数列的顶端

    步骤:

    1)将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)

    2)对序列当中剩下的n-1个元素再次执行步骤1。

    3)持续每次对越来越少的元素进行重复上面的步骤直到没有任何一对数字需要比较

    void swap(int a[], int i, int j)
    {
    	int temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    }
    //冒泡
    void BubbleSort(int a[], int size)
    {
    	for (int i = 0; i < size - 1; ++i)
    	{
    		for (int j = 0; j < size - 1 - i; ++j)
    		{
    			if (a[j] < a[j + 1]){
    				swap(a,j,j+1);
    			}
    		}
    	}
    }
    //鸡尾酒排序 分两部分1)将最大的元素放在后面 2)将最小的元素放在前面
    void Bubblesort(int a[], int size)
    {
    	int left = 0;
    	int right = size - 1;
    	while (left<right)
    	{
    		for (int i = 0; i < right; i++)
    		{
    			if (a[i]<a[i + 1])
    			{
    				swap(a, i, i + 1);
    			}
    		}
    		right--;
    		for (int j = right; j>left; j--)
    		{
    			if (a[j - 1] < a[j])
    			{
    				swap(a, j - 1, j);
    			}
    		}
    		left++;
    	}
    }

    基数排序

    基数排序:通过序列中各个元素的值,对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

    分配:我们将L[i]中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中

    收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]

    对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位,则排序结束

     

    附加上各种排序算法的稳定性以及空间/时间复杂度

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 数据结构几种常见排序算法之比较,比较常见的冒泡排序、快速排序等
  • 数据结构课程设计 实验报告 内部排序算法比较、数据结构课程设计
  • 数据结构常用种排序算法

    万次阅读 多人点赞 2018-04-14 12:02:23
    排序有内部排序和外部排序,内部排序数据记录在内存中进行排序,而外部排序是因排序数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。   ...

    概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    我们这里说说八大排序就是内部排序。


        

        当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


     

    1.插入排序—直接插入排序(Straight Insertion Sort)

    基本思想:

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    直接插入排序示例:



    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    算法的实现:

    [cpp]  view plain  copy
    1. void print(int a[], int n ,int i){  
    2.     cout<<i <<":";  
    3.     for(int j= 0; j<8; j++){  
    4.         cout<<a[j] <<" ";  
    5.     }  
    6.     cout<<endl;  
    7. }  
    8.   
    9.   
    10. void InsertSort(int a[], int n)  
    11. {  
    12.     for(int i= 1; i<n; i++){  
    13.         if(a[i] < a[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
    14.             int j= i-1;   
    15.             int x = a[i];        //复制为哨兵,即存储待排序元素  
    16.             a[i] = a[i-1];           //先后移一个元素  
    17.             while(x < a[j]){  //查找在有序表的插入位置  
    18.                 a[j+1] = a[j];  
    19.                 j--;         //元素后移  
    20.             }  
    21.             a[j+1] = x;      //插入到正确位置  
    22.         }  
    23.         print(a,n,i);           //打印每趟排序的结果  
    24.     }  
    25.       
    26. }  
    27.   
    28. int main(){  
    29.     int a[8] = {3,1,5,7,2,4,9,6};  
    30.     InsertSort(a,8);  
    31.     print(a,8,8);  
    32. }  

    效率:

    时间复杂度:O(n^2).

    其他的插入排序有二分插入排序,2-路插入排序。

     

     2. 插入排序—希尔排序(Shell`s Sort)

    希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

    基本思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    操作方法:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    希尔排序的示例:


    算法实现:

     

    我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

    即:先将要排序的一组记录按某个增量dn/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

    [cpp]  view plain  copy
    1. void print(int a[], int n ,int i){  
    2.     cout<<i <<":";  
    3.     for(int j= 0; j<8; j++){  
    4.         cout<<a[j] <<" ";  
    5.     }  
    6.     cout<<endl;  
    7. }  
    8. /** 
    9.  * 直接插入排序的一般形式 
    10.  * 
    11.  * @param int dk 缩小增量,如果是直接插入排序,dk=1 
    12.  * 
    13.  */  
    14.   
    15. void ShellInsertSort(int a[], int n, int dk)  
    16. {  
    17.     for(int i= dk; i<n; ++i){  
    18.         if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
    19.             int j = i-dk;     
    20.             int x = a[i];           //复制为哨兵,即存储待排序元素  
    21.             a[i] = a[i-dk];         //首先后移一个元素  
    22.             while(x < a[j]){     //查找在有序表的插入位置  
    23.                 a[j+dk] = a[j];  
    24.                 j -= dk;             //元素后移  
    25.             }  
    26.             a[j+dk] = x;            //插入到正确位置  
    27.         }  
    28.         print(a, n,i );  
    29.     }  
    30.       
    31. }  
    32.   
    33. /** 
    34.  * 先按增量d(n/2,n为要排序数的个数进行希尔排序 
    35.  * 
    36.  */  
    37. void shellSort(int a[], int n){  
    38.   
    39.     int dk = n/2;  
    40.     while( dk >= 1  ){  
    41.         ShellInsertSort(a, n, dk);  
    42.         dk = dk/2;  
    43.     }  
    44. }  
    45. int main(){  
    46.     int a[8] = {3,1,5,7,2,4,9,6};  
    47.     //ShellInsertSort(a,8,1); //直接插入排序  
    48.     shellSort(a,8);           //希尔插入排序  
    49.     print(a,8,8);  
    50. }  

    希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的 增量因子序列的方法。 增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意: 增量因子中除1 外没有公因子,且最后一个 增量因子必须为1。希尔排序方法是一个不稳定的排序方法。


    3. 选择排序—简单选择排序(Simple Selection Sort)

    基本思想:

    在要排序的一组数中,选出最小(或者最大)的个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后个数)比较为止。

    简单选择排序的示例:

     

    操作方法:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。


    算法实现:

    [cpp]  view plain  copy
    1. void print(int a[], int n ,int i){  
    2.     cout<<"第"<<i+1 <<"趟 : ";  
    3.     for(int j= 0; j<8; j++){  
    4.         cout<<a[j] <<"  ";  
    5.     }  
    6.     cout<<endl;  
    7. }  
    8. /** 
    9.  * 数组的最小值 
    10.  * 
    11.  * @return int 数组的键值 
    12.  */  
    13. int SelectMinKey(int a[], int n, int i)  
    14. {  
    15.     int k = i;  
    16.     for(int j=i+1 ;j< n; ++j) {  
    17.         if(a[k] > a[j]) k = j;  
    18.     }  
    19.     return k;  
    20. }  
    21.   
    22. /** 
    23.  * 选择排序 
    24.  * 
    25.  */  
    26. void selectSort(int a[], int n){  
    27.     int key, tmp;  
    28.     for(int i = 0; i< n; ++i) {  
    29.         key = SelectMinKey(a, n,i);           //选择最小的元素  
    30.         if(key != i){  
    31.             tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
    32.         }  
    33.         print(a,  n , i);  
    34.     }  
    35. }  
    36. int main(){  
    37.     int a[8] = {3,1,5,7,2,4,9,6};  
    38.     cout<<"初始值:";  
    39.     for(int j= 0; j<8; j++){  
    40.         cout<<a[j] <<"  ";  
    41.     }  
    42.     cout<<endl<<endl;  
    43.     selectSort(a, 8);  
    44.     print(a,8,8);  
    45. }  

     简单选择排序的改进——二元选择排序

    简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。具体实现如下:

    [cpp]  view plain  copy
    1. void SelectSort(int r[],int n) {  
    2.     int i ,j , min ,max, tmp;  
    3.     for (i=1 ;i <= n/2;i++) {    
    4.         // 做不超过n/2趟选择排序   
    5.         min = i; max = i ; //分别记录最大和最小关键字记录位置  
    6.         for (j= i+1; j<= n-i; j++) {  
    7.             if (r[j] > r[max]) {   
    8.                 max = j ; continue ;   
    9.             }    
    10.             if (r[j]< r[min]) {   
    11.                 min = j ;   
    12.             }     
    13.       }    
    14.       //该交换操作还可分情况讨论以提高效率  
    15.       tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
    16.       tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
    17.   
    18.     }   
    19. }  

    4. 选择排序—堆排序(Heap Sort)

    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足


    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)



    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:



    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
                                  


                                  

     

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    [cpp]  view plain  copy
    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8.   
    9.   
    10. /** 
    11.  * 已知H[s…m]除了H[s] 外均满足堆的定义 
    12.  * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
    13.  * 
    14.  * @param H是待调整的堆数组 
    15.  * @param s是待调整的数组元素的位置 
    16.  * @param length是数组的长度 
    17.  * 
    18.  */  
    19. void HeapAdjust(int H[],int s, int length)  
    20. {  
    21.     int tmp  = H[s];  
    22.     int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
    23.     while (child < length) {  
    24.         if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
    25.             ++child ;  
    26.         }  
    27.         if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
    28.             H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点  
    29.             s = child;       // 重新设置s ,即待调整的下一个结点的位置  
    30.             child = 2*s+1;  
    31.         }  else {            // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出  
    32.              break;  
    33.         }  
    34.         H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
    35.     }  
    36.     print(H,length);  
    37. }  
    38.   
    39.   
    40. /** 
    41.  * 初始堆进行调整 
    42.  * 将H[0..length-1]建成堆 
    43.  * 调整完之后第一个元素是序列的最小的元素 
    44.  */  
    45. void BuildingHeap(int H[], int length)  
    46. {   
    47.     //最后一个有孩子的节点的位置 i=  (length -1) / 2  
    48.     for (int i = (length -1) / 2 ; i >= 0; --i)  
    49.         HeapAdjust(H,i,length);  
    50. }  
    51. /** 
    52.  * 堆排序算法 
    53.  */  
    54. void HeapSort(int H[],int length)  
    55. {  
    56.     //初始堆  
    57.     BuildingHeap(H, length);  
    58.     //从最后一个元素开始对序列进行调整  
    59.     for (int i = length - 1; i > 0; --i)  
    60.     {  
    61.         //交换堆顶元素H[0]和堆中最后一个元素  
    62.         int temp = H[i]; H[i] = H[0]; H[0] = temp;  
    63.         //每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整  
    64.         HeapAdjust(H,0,i);  
    65.   }  
    66. }   
    67.   
    68. int main(){  
    69.     int H[10] = {3,1,5,7,2,4,9,6,10,8};  
    70.     cout<<"初始值:";  
    71.     print(H,10);  
    72.     HeapSort(H,10);  
    73.     //selectSort(a, 8);  
    74.     cout<<"结果:";  
    75.     print(H,10);  
    76.   
    77. }  


    分析:

    设树深度为k,。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式: 

                                    

    而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。

     

    5. 交换排序—冒泡排序(Bubble Sort)

    基本思想:

    在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

    冒泡排序的示例:

     

    算法的实现:

    [cpp]  view plain  copy
    1. void bubbleSort(int a[], int n){  
    2.     for(int i =0 ; i< n-1; ++i) {  
    3.         for(int j = 0; j < n-i-1; ++j) {  
    4.             if(a[j] > a[j+1])  
    5.             {  
    6.                 int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
    7.             }  
    8.         }  
    9.     }  
    10. }  


    冒泡排序算法的改进

    对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    [cpp]  view plain  copy
    1. void Bubble_1 ( int r[], int n) {  
    2.     int i= n -1;  //初始时,最后位置保持不变  
    3.     while ( i> 0) {   
    4.         int pos= 0; //每趟开始时,无记录交换  
    5.         for (int j= 0; j< i; j++)  
    6.             if (r[j]> r[j+1]) {  
    7.                 pos= j; //记录交换的位置   
    8.                 int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
    9.             }   
    10.         i= pos; //为下一趟排序作准备  
    11.      }   
    12. }    

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    改进后的算法实现为:

    [cpp]  view plain  copy
    1. void Bubble_2 ( int r[], int n){  
    2.     int low = 0;   
    3.     int high= n -1; //设置变量的初始值  
    4.     int tmp,j;  
    5.     while (low < high) {  
    6.         for (j= low; j< high; ++j) //正向冒泡,找到最大者  
    7.             if (r[j]> r[j+1]) {  
    8.                 tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
    9.             }   
    10.         --high;                 //修改high值, 前移一位  
    11.         for ( j=high; j>low; --j) //反向冒泡,找到最小者  
    12.             if (r[j]<r[j-1]) {  
    13.                 tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;  
    14.             }  
    15.         ++low;                  //修改low值,后移一位  
    16.     }   
    17. }   

    6. 交换排序—快速排序(Quick Sort)

    基本思想:

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程


    算法的实现:

     递归实现:

    [cpp]  view plain  copy
    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8. void swap(int *a, int *b)  
    9. {  
    10.     int tmp = *a;  
    11.     *a = *b;  
    12.     *b = tmp;  
    13. }  
    14.   
    15. int partition(int a[], int low, int high)  
    16. {  
    17.     int privotKey = a[low];                             //基准元素  
    18.     while(low < high){                                   //从表的两端交替地向中间扫描  
    19.         while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
    20.         swap(&a[low], &a[high]);  
    21.         while(low < high  && a[low] <= privotKey ) ++low;  
    22.         swap(&a[low], &a[high]);  
    23.     }  
    24.     print(a,10);  
    25.     return low;  
    26. }  
    27.   
    28.   
    29. void quickSort(int a[], int low, int high){  
    30.     if(low < high){  
    31.         int privotLoc = partition(a,  low,  high);  //将表一分为二  
    32.         quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
    33.         quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    34.     }  
    35. }  
    36.   
    37. int main(){  
    38.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    39.     cout<<"初始值:";  
    40.     print(a,10);  
    41.     quickSort(a,0,9);  
    42.     cout<<"结果:";  
    43.     print(a,10);  
    44.   
    45. }  


    分析:

    快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

     
    快速排序的改进

    在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下:

    [cpp]  view plain  copy
    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8. void swap(int *a, int *b)  
    9. {  
    10.     int tmp = *a;  
    11.     *a = *b;  
    12.     *b = tmp;  
    13. }  
    14.   
    15. int partition(int a[], int low, int high)  
    16. {  
    17.     int privotKey = a[low];                 //基准元素  
    18.     while(low < high){                   //从表的两端交替地向中间扫描  
    19.         while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
    20.         swap(&a[low], &a[high]);  
    21.         while(low < high  && a[low] <= privotKey ) ++low;  
    22.         swap(&a[low], &a[high]);  
    23.     }  
    24.     print(a,10);  
    25.     return low;  
    26. }  
    27.   
    28.   
    29. void qsort_improve(int r[ ],int low,int high, int k){  
    30.     if( high -low > k ) { //长度大于k时递归, k为指定的数  
    31.         int pivot = partition(r, low, high); // 调用的Partition算法保持不变  
    32.         qsort_improve(r, low, pivot - 1,k);  
    33.         qsort_improve(r, pivot + 1, high,k);  
    34.     }   
    35. }   
    36. void quickSort(int r[], int n, int k){  
    37.     qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序  
    38.   
    39.     //再用插入排序对基本有序序列排序  
    40.     for(int i=1; i<=n;i ++){  
    41.         int tmp = r[i];   
    42.         int j=i-1;  
    43.         while(tmp < r[j]){  
    44.             r[j+1]=r[j]; j=j-1;   
    45.         }  
    46.         r[j+1] = tmp;  
    47.     }   
    48.   
    49. }   
    50.   
    51.   
    52.   
    53. int main(){  
    54.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    55.     cout<<"初始值:";  
    56.     print(a,10);  
    57.     quickSort(a,9,4);  
    58.     cout<<"结果:";  
    59.     print(a,10);  
    60.   
    61. }  


    7. 归并排序(Merge Sort)


    基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    归并排序示例:

     


    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵
    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
    5. 合并结束。
    [cpp]  view plain  copy
    1. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
    2. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
    3. {  
    4.     int j,k;  
    5.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
    6.         if(r[j] < r[i]) rf[k] = r[j++];  
    7.         else rf[k] = r[i++];  
    8.     }  
    9.     while(i <= m)  rf[k++] = r[i++];  
    10.     while(j <= n)  rf[k++] = r[j++];  
    11. }  


    归并的迭代算法


    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    [cpp]  view plain  copy
    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
    9. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
    10. {  
    11.     int j,k;  
    12.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
    13.         if(r[j] < r[i]) rf[k] = r[j++];  
    14.         else rf[k] = r[i++];  
    15.     }  
    16.     while(i <= m)  rf[k++] = r[i++];  
    17.     while(j <= n)  rf[k++] = r[j++];  
    18.     print(rf,n+1);  
    19. }  
    20.   
    21. void MergeSort(ElemType *r, ElemType *rf, int lenght)  
    22. {   
    23.     int len = 1;  
    24.     ElemType *q = r ;  
    25.     ElemType *tmp ;  
    26.     while(len < lenght) {  
    27.         int s = len;  
    28.         len = 2 * s ;  
    29.         int i = 0;  
    30.         while(i+ len <lenght){  
    31.             Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
    32.             i = i+ len;  
    33.         }  
    34.         if(i + s < lenght){  
    35.             Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
    36.         }  
    37.         tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf  
    38.     }  
    39. }  
    40.   
    41.   
    42. int main(){  
    43.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    44.     int b[10];  
    45.     MergeSort(a, b, 10);  
    46.     print(b,10);  
    47.     cout<<"结果:";  
    48.     print(a,10);  
    49.   
    50. }  

    两路归并的递归算法

    [cpp]  view plain  copy
    1. void MSort(ElemType *r, ElemType *rf,int s, int t)  
    2. {   
    3.     ElemType *rf2;  
    4.     if(s==t) r[s] = rf[s];  
    5.     else  
    6.     {   
    7.         int m=(s+t)/2;          /*平分*p 表*/  
    8.         MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
    9.         MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
    10.         Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    11.     }  
    12. }  
    13. void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
    14. {   /*对顺序表*p 作归并排序*/  
    15.     MSort(r, rf,0, n-1);  
    16. }  

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。


    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                   

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。


    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    算法实现:

    [cpp]  view plain  copy
    1. Void RadixSort(Node L[],length,maxradix)  
    2. {  
    3.    int m,n,k,lsp;  
    4.    k=1;m=1;  
    5.    int temp[10][length-1];  
    6.    Empty(temp); //清空临时空间  
    7.    while(k<maxradix) //遍历所有关键字  
    8.    {  
    9.      for(int i=0;i<length;i++) //分配过程  
    10.     {  
    11.        if(L[i]<m)  
    12.           Temp[0][n]=L[i];  
    13.        else  
    14.           Lsp=(L[i]/m)%10; //确定关键字  
    15.        Temp[lsp][n]=L[i];  
    16.        n++;  
    17.    }  
    18.    CollectElement(L,Temp); //收集  
    19.    n=0;  
    20.    m=m*10;  
    21.   k++;  
    22.  }  
    23. }  





    总结

    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:



                                 时间复杂度函数O(n)的增长情况


    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。


    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序堆排序归并排序
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至On);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为On2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。

      2
    、记录的关键字位数较少,如果密集更好

      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。


    转载出处:http://blog.csdn.net/hguisu/article/details/7776068

    展开全文
  • 目录一、实验目的和要求二、实验环境三、实验内容四、实验过程4.1 任务定义和问题分析4.2 数据结构的选择和概要设计五、测试及结果分析5.1 实验数据5.2 结果及分析六、实验收获八、附录(源代码) 一、实验目的和...

    一、实验目的和要求

    目的:给出一组实验来比较排序算法的时间性能
    要求:
    (1)时间性能
    (2)实验数据应具有说服力
    (3)实验结果要能以清晰的形式给出,如图、表等。
    (4)算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。
    (5)实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。
    (6)要给出实验的方案及其分析。

    二、实验环境

    软件环境:visual stdio 2017
    硬件环境:①CPU:Intel(R)Core(TM)i7-8565U CPU @1.80Ghz
    ②内存:8.0GB

    三、实验内容

    给出一组实验来比较排序算法的时间性能

    四、实验过程

    4.1 任务定义和问题分析

    选取若干个排序算法,对每种算法进行大量数据测试,同一规模的数据进行3次测试取平均值,最终得到若干个实验数据,进行绘图展示。

    4.2 数据结构的选择和概要设计

    本次实验选取直接插入排序,希尔排序,冒泡排序,快速排序,直接选择排序,堆排序,归并排序这7种算法。
    分为2个大实验组,第一个大实验组为算法时间复杂度为O(n²)的算法,其中有直接插入排序,冒泡排序,直接选择排序。
    第二个实验组为算法时间复杂度为O(nlogn)的算法,其中有希尔排序,快速排序,堆排序,归并排序。
    4.3 详细设计
    在第一个实验组中,选取规模分别为1000,5000,10000,50000,75000,100000,125000,175000,200000,250000的数据,每种数据测试三次取平均值。
    在第二个实验组中,选取规模分别为10000,100000,200000,250000,500000,600000,750000,900000,1000000,10000000,25000000,30000000,40000000,50000000,60000000,75000000,100000000的数据,每种数据测试三次取平均值。在这些数据中,以1000000为分界点,分别制图。
    制图采用python中的matplotlib工具,制作曲线图。
    在这里插入图片描述

    • 直接插入排序
    template<typename T>
    void insert_sort(T array[], int n)
    {
    	for (int i = 1; i < n; i++)
    	{
    		T temp = array[i];
    		int j = i - 1;
    		while (array[j] > temp&&j >= 0)
    			array[j + 1] = array[j--];
    		array[j + 1] = temp;
    	}
    }
    
    • 希尔排序
    template<typename T>
    void shell_sort(T array[], int n)
    {
    	int d = n / 2;
    	while (d > 0)
    	{
    		for (int i = d; i < n; i++)
    		{
    			T temp = array[i];
    			int j = i - d;
    			while (j >= 0 && temp < array[j])
    			{
    				array[j + d] = array[j];
    				j -= d;
    			}
    			array[j + d] = temp;
    		}
    		d = d / 2;
    	}
    }
    
    • 冒泡排序
    template<typename T>
    void bubble_sort(T array[],int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		for (int j = 0; j < n - 1 - i; j++)
    		{
    			if (array[j] > array[j + 1])
    			{
    				T temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    		}
    	}
    }
    
    • 快速排序
    template<typename T>
    void quick_sort(T array[], int left, int right)
    {
    	if (left >= right) return;
    	int i = left, j = right;
    	T temp = array[left];
    	while (i != j)
    	{
    		while (array[j] > temp&&j > i) j--;
    		if (i < j) array[i++] = array[j];
    		while (array[i] < temp&&i < j) i++;
    		if (i < j) array[j--] = array[i];
    
    	}
    	array[i] = temp;
    	quick_sort(array, i + 1, right);
    	quick_sort(array, left, i - 1);
    }
    
    • 直接选择排序
    template<typename T>
    void select_sort(T array[],int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		int index = i;
    		for (int j = i + 1; j < n; j++)
    		{
    			if (array[j] < array[index])
    				index = j;
    		}
    		if (i != index)
    		{
    			T temp = array[i];
    			array[i] = array[index];
    			array[index] = temp;
    		}
    	}
    }
    
    • 归并排序
    template<typename T>
    void merge_sort(T array[], int left, int right)
    {
    	if (left >= right) return;
    	int mid = (left + right) / 2;
    	merge_sort(array, left, mid);
    	merge_sort(array, mid + 1, right);
    	int i = left, k = left, j = mid + 1;
    	while (i <= mid&&j <= right)
    	{
    		if (array[i] < array[j]) assist[k++] = array[i++];
    		else assist[k++] = array[j++];
    	}
    	while (i <= mid)
    		assist[k++] = array[i++];
    	while (j <= right)
    		assist[k++] = array[j++];
    	for (int k = left; k <= right; k++)
    		array[k] = assist[k];
    }
    
    • 堆排序
    template<typename T>
    void swap(T arr[], int a, int b)		
    {
    	T temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    template<typename T>
    void adjustHeap(T arr[], int i, int length)		
    {
    	T temp = arr[i];
    	for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
    	{
    		if (k + 1 < length&&arr[k] < arr[k + 1]) k++;
    		if (arr[k] > temp)
    		{
    			arr[i] = arr[k];
    			i = k;
    		}
    		else break;
    	}
    	arr[i] = temp;
    }
    
    template<typename T>
    void heap_sort(T arr[], int length)
    {
    	for (int i = length / 2 - 1; i >= 0; i--)
    		adjustHeap(arr, i, length);
    	for (int j = length - 1; j > 0; j--)
    	{
    		swap(arr, 0, j);
    		adjustHeap(arr, 0, j);
    	}
    
    }
    

    五、测试及结果分析

    5.1 实验数据

    数据规模详见上述分析,具体数据由随机数产生,范围为0~1073283121( rand()*rand() )。

    5.2 结果及分析

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    分析:
    在图像中可以清晰地看出每种算法的时间复杂度。
    先进行纵向对比,可以发现三种O(n²)的算法在数据规模达到250000时的排序用时便已全部超过20s,而O(nlogn)的算法在数据规模达到40000000时的排序用时才开始出现超过20s的现象,二者差异巨大。

    故:时间复杂度为O(nlogn)的算法的时间性能远远大于O(n²)时间复杂度算法的时间性能

    再进行横向对比,可以发现:时间复杂度为O(n²)的算法中,各算法对相同规模的数据的排序时间有T(冒泡排序)>T(选择排序)>T(插入排序),时间复杂度为O(nlogn)的算法中,各算法对相同规模的数据的排序时间有T(希尔排序)>T(堆排序)>T(归并排序)>T(快速排序)
    故:相同时间复杂度的算法在进行相同规模数据排序时,是有差异的,这种差异随着数据规模的增加愈发明显。在O(n²)的算法中,插入排序优于选择排序,选择排序优于冒泡排序;在O(nlogn)的算法中,快速排序优于归并排序,归并排序优于堆排序,堆排序优于希尔排序

    六、实验收获

    在本次实验中,我通过数据,清晰地认识到了不同时间复杂度的算法在处理大规模数据时的差异,同时也认识到,时间复杂度是相对的,尽管时间复杂度的等级相同,但在运行时所耗费的时间也会有差异。本次实验启示我以后在解决问题设计算法的时候,不仅要考虑时间复杂度的等级,也需要关注实际语句的执行次数,对其优化,达到最优。

    八、附录(源代码)

    #include<iostream>
    #include<cstdlib>
    #include<ctime>
    using namespace std;
    const int N = 100000 * 1000;
    int a[N];
    int assist[N];
    
    template<typename T>
    void print(T array[],int n)
    {
    	for (int i = 0; i < n; i++)
    		cout << array[i] << " ";
    	cout << endl;
    }
    
    template<typename T>
    void insert_sort(T array[], int n)
    {
    	for (int i = 1; i < n; i++)
    	{
    		T temp = array[i];
    		int j = i - 1;
    		while (array[j] > temp&&j >= 0)
    			array[j + 1] = array[j--];
    		array[j + 1] = temp;
    	}
    }
    
    template<typename T>
    void shell_sort(T array[], int n)
    {
    	int d = n / 2;
    	while (d > 0)
    	{
    		for (int i = d; i < n; i++)
    		{
    			T temp = array[i];
    			int j = i - d;
    			while (j >= 0 && temp < array[j])
    			{
    				array[j + d] = array[j];
    				j -= d;
    			}
    			array[j + d] = temp;
    		}
    		d = d / 2;
    	}
    }
    
    template<typename T>
    void bubble_sort(T array[],int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		for (int j = 0; j < n - 1 - i; j++)
    		{
    			if (array[j] > array[j + 1])
    			{
    				T temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    		}
    	}
    }
    
    template<typename T>
    void quick_sort(T array[], int left, int right)
    {
    	if (left >= right) return;
    	int i = left, j = right;
    	T temp = array[left];
    	while (i != j)
    	{
    		while (array[j] > temp&&j > i) j--;
    		if (i < j) array[i++] = array[j];
    		while (array[i] < temp&&i < j) i++;
    		if (i < j) array[j--] = array[i];
    
    	}
    	array[i] = temp;
    	quick_sort(array, i + 1, right);
    	quick_sort(array, left, i - 1);
    }
    
    template<typename T>
    void select_sort(T array[],int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		int index = i;
    		for (int j = i + 1; j < n; j++)
    		{
    			if (array[j] < array[index])
    				index = j;
    		}
    		if (i != index)
    		{
    			T temp = array[i];
    			array[i] = array[index];
    			array[index] = temp;
    		}
    	}
    }
    
    template<typename T>
    void merge_sort(T array[], int left, int right)
    {
    	if (left >= right) return;
    	int mid = (left + right) / 2;
    	merge_sort(array, left, mid);
    	merge_sort(array, mid + 1, right);
    	int i = left, k = left, j = mid + 1;
    	while (i <= mid&&j <= right)
    	{
    		if (array[i] < array[j]) assist[k++] = array[i++];
    		else assist[k++] = array[j++];
    	}
    	while (i <= mid)
    		assist[k++] = array[i++];
    	while (j <= right)
    		assist[k++] = array[j++];
    	for (int k = left; k <= right; k++)
    		array[k] = assist[k];
    }
    
    template<typename T>
    void swap(T arr[], int a, int b)		
    {
    	T temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    template<typename T>
    void adjustHeap(T arr[], int i, int length)		
    {
    	T temp = arr[i];
    	for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
    	{
    		if (k + 1 < length&&arr[k] < arr[k + 1]) k++;
    		if (arr[k] > temp)
    		{
    			arr[i] = arr[k];
    			i = k;
    		}
    		else break;
    	}
    	arr[i] = temp;
    }
    
    template<typename T>
    void heap_sort(T arr[], int length)
    {
    	for (int i = length / 2 - 1; i >= 0; i--)
    		adjustHeap(arr, i, length);
    	for (int j = length - 1; j > 0; j--)
    	{
    		swap(arr, 0, j);
    		adjustHeap(arr, 0, j);
    	}
    
    }
    
    int main()
    {
    	srand(time(0));
    	for (int i = 0; i < N; i++)
    		a[i] = rand()*rand();
    	clock_t begin = clock();
    	//merge_sort(a, 0, N - 1);
    	heap_sort(a, N);
    	clock_t end = clock();
    	//print(a, N);
    	cout << N << "个数据用时为" << double(end - begin) / CLOCKS_PER_SEC << "s" << endl;
    	return 0;
    }
    
    展开全文
  • 数据结构】各种排序算法&各种排序算法的比较

    千次阅读 多人点赞 2019-05-25 21:29:32
    冒泡排序(Bubble Sort): 对于一串数字,如3 2 5 9 6 4 1 从3的位置开始往后进行 如果被比较数比3小,那么那个数就“浮上去”,即与3进行交换,此时变成 2 3 5 9 6 4 1 再从第二个位置开始,即3和5比,顺序正常 第...
  • 几种常见排序算法的实现与性能分析数据结构课程设计报告.doc
  • 今天看到了一个算法,感觉以前学过的呢些算法都忘得差不多了,下午复习复习,忘记的上网搜搜,下面的全部编译通过,又学习了点东西。
  • 课程设计(论文) @ 题 目 名 称 几种常见排序算法的实现与性能分析 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 专 业 信息工程系通信工程 指 导 教 师 年 摘 要 设计一个测试程序比较起泡排序直接排序简单...
  • 一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....
  • 综述 完整代码-顺序表版本 完整代码-链表版本 交换排序 冒泡排序 ...内排序是指所有的数据已经读入内存,在内存中进行排序算法排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用...
  • 数据结构课程设计报告几种排序算法的演示(附源代第四次实验码)毕业论文.doc
  • 本周的实验主要做快速排序自己随机生成 10000 个数 据用快速排序算法输出排序完成所需时间 再用其他 排序方法做比较至少完成两个算法的效率比较 数据结构课程设计报告 几种排序算法的演示 时间 2010-1-14 一 需求...
  • 举例:现在要排序1,2,2这三个数,我们用A算法排序,如果排序后两个2的位置不会互换,则A算法是稳定的,如果互换了,则A算法就是不稳定的。 稳定排序有哪些: 冒泡、插入、归并、二叉树排序都是稳定排序。 不稳定...
  • 数据结果中,实现排序的方法,有快速排序,希尔排序,直接排序,直接插入排序,气泡排序,选择排序等等!
  • 数据结构 常用八大排序算法及代码实现

    万次阅读 多人点赞 2018-08-13 19:58:39
    一、排序的介绍 1. 排序的分类 按照排序过程中所依据的原则的不同可以分类为: ►插入排序:直接插入...2. 排序算法比较 排序方法 最好时间 平均时间 最坏时间 ...
  • 这里写目录标题实验目的实验内容实验要求六种排序方法细解直接插入排序冒泡排序简单选择排序希尔排序快速排序归并排序六种排序好坏分析代码段运行结果 实验目的 1.能够清楚表述主要内部排序方法的设计思路。 2....
  • 下面我们通过一个实验案例来进行上述4种排序算法效率的直观比较。 实验内容:创建4个具有相同初始化长度、初始化元素内容和元素顺序的,长度为100000的正整数数组,数组中填充的全部都是取值范围在[0,100000]之间的...
  • 设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 【基本要求】 (1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数...
  • 一、排序的概念: 1、设 n 个记录的序列为 { R1 , R2 , R3 , . . . , Rn} 其相应的关键字序列为 { K1 , K2 , K3, . . . , Kn } 若规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn,使得相应的...
  • (1)对以下6种常用的内部排序算法进行比较z起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 (2)待排序表的表长不小于1005其中的数据要用伪随机数产生程序产生:至少要用5组不同的输入数据作比较...
  • 数据结构6内部排序算法的比较

    千次阅读 2017-03-19 10:46:14
    1、需求分析(1)输入数据的形式为...对起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这6种常用的内部排序算法进行比较,比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3
  • 数据结构中各种排序算法比较

    千次阅读 2017-11-08 16:02:49
    快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快 速排序可以由下面四步组成。     ( 1 )   如果不多于 1 个数据,直接返回。   ( 2 )   一般选择序列最...
  • 几种排序算法是在顺序存储结构上实现的,因此在排序过程中需要进行大量记录的移动。当记录很大时,时间耗费很大,此时可采用静态链表作存储结构。但是有的排序方法,无法实现表排序。在这种情况下可以进行地址...
  • 山东大学 数据结构 实验2 排序算法

    千次阅读 2018-11-19 21:17:23
    实验二 排序算法 一、 要求完成时间 实验开始后的第三周之前完成 二、 实验目的 掌握各种排序方法的实现思想。 三、 实验内容  1、 输入2-20个不为零的正整数,遇到0代表输入结束,0不参与排序。  2、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 200,188
精华内容 80,075
关键字:

数据结构几种常用的排序算法实验

数据结构 订阅