排序算法的研究总结

2018/03/06 17:30
阅读数 14

前言:闲来无事,便研究起来对数组的排序算法,怕过后遗忘,特地总结一下,也希望能帮到大家

概要: 

总结的算法:

冒泡排序、插入排序、选择排序

要排序的一列数(从小到大):

1, 5, 3, 83, 46, 55, 16, 87, 28, 66, 8, 33, 47

 

一、冒泡排序

1.源代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BubbleSort
{
    class Program
    {
        static void Main(string[] args)
        {
            //定义要排序的数组
            int[] iArrary = new int[] { 1, 5, 3, 83, 46, 55, 16, 87, 28, 66, 8, 33, 47 };

            Program pg = new Program();

            //给数组排序
            pg.Sort(iArrary);

            //排序后循环输出数组
            foreach (int item in iArrary)
            {
                Console.WriteLine(item);


            }
            //防止控制台一闪而过
            Console.ReadLine();
        

        }

        public void Sort(IList<int> data)
        {
            //从第一个数(i = 0)开始,循环整个数组。
            for (int i = 0; i < data.Count; i++)
            {
                //从最后一个数开始,到第(i+1)个数结束,依次比较相邻的两个数,
                //如果前一个数大于后一个数,就交换他们两个
                //这样,第一个循环下来,第一个数是最小的数
                //第二个循环下来,第二个数是第二小的数。。。依次类推
                for (int j = data.Count-1; j > i; j--)
                {
                    if (data[j - 1] > data[j])
                    {
                        int temp;
                        temp = data[j - 1];
                        data[j - 1] = data[j];
                        data[j] = temp;

                    }
              
                  
                
                }
            }
        }
    }
}

2 .运行结果

 

 

 

 

二、插入排序

1.算法简介

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2.算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • <1>.从第一个元素开始,该元素可以认为已经被排序;
  • <2>.取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • <3>.如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • <4>.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • <5>.将新元素插入到该位置后;
  • <6>.重复步骤2~5。

3.源代码

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

            Program pg = new Program();

            pg.InsrtSort(iArrary);

              foreach (int item in iArrary)
            {
                Console.WriteLine(item);

            
            }
              Console.ReadLine();
        
        }

        //插入排序
        public void InsrtSort(IList<int> data)
        {
            // int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
            int temp;

            for (int i = 1; i < data.Count; i++)
            {
                temp = data[i];//要与已排序数组比较的新元素

                //从0到j,代表的是已排序的数
                for (int j = i - 1; j >= 0; j--)
                {

                    if (data[j] > temp)//新元素小于该元素(已排序),将该元素移到下一位置
                    {
                        data[j + 1] = data[j];
                        //data[j] = temp;
                        if (j == 0)//因为取不到 j==0 的值,故在此做特殊处理
                        {
                            data[0] = temp;//只有当第二个数小于第一个数的时候,才会执行该处代码
                        }
                    }
                    else//否则,将新元素移到下一位置
                    {
                        data[j + 1] = temp;
                        break;//跳出里面的循环
                    
                    }
                
                }
            }

       
        }

    }
}

 

4.运行结果

 

 

 

三. 选择排序

1.思路

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

然后,再从剩余未排序元素中,继续寻找最小元素,然后放到已排序序列的末尾。

以此类推,直到所有元素排序完毕。

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SelectionSort
{
    class Program
    {
        static void Main(string[] args)
        {

            int[] iArrary = new int[] { 1, 5, 3, 83, 46, 55, 16, 87, 28, 66, 8, 33, 47 };

            Program pg = new Program();

            pg.Sort(iArrary);

            foreach (int item in iArrary)
            {
                Console.WriteLine(item);


            }
            Console.ReadLine();

        }
        public void Sort(IList<int> data)
        {
            // int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
            for (int i = 0; i < data.Count - 1; i++)
            {
                //在未排序序列中,总是默认为第一个值,为最小值;min 与temp都是过来跑龙套的
                int min = i;//最小值的序号
                int temp = data[i];//最小值

                //找到剩余未排序元素的最小值
                for (int j = i+1; j < data.Count; j++)
                {
                    if (data[j] < temp)//剩余未排序元素中,存在某元素数小于最小值
                    {
                        min = j;
                        temp = data[j];//将该元素的值认为是最小值
                    }           
                
                }

                if (min != i)//
                {
                    int t = data[min];
                    data[min] = data[i];
                    data[i] = t;//将找到的最小值放入已排序序列的末尾

                }
            
            }
        
        }

    }
}

 

3.运行结果

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部