排序算法（转）

（1）插入排序

插入排序是逐个处理待排序的记录，每个新记录与前面已排序的子序列进行比较，将它插入到子序列中正确的位置，如下图所示。

View Code

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

namespace studyCSharp
{
    class Program
    {
        static void Main(string[] args)
        {
         int[] a={6,5,4,7,9,8,10,3,2,1};//待排序的数组            
         int temp;//临时变量
         for(int i=0;i<9;i++)
         {
          for(int j=i;j>=0;j--)
           if(a[j+1]<a[j])
           {
            //交换值
               temp=a[j];
               a[j]=a[j+1];
               a[j+1]=temp;
           }
           else
               break;
         }
      //输出排序后的数组
          for(int i=0;i<10;i++)
          Console.Write(string.Format("{0},",a[i]));
        }
    }
}

（2）冒泡排序

View Code

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

namespace studyCSharp
{
    class Program
    {
        static void Main(string[] args)
        {
         int[] a={6,5,4,7,9,8,10,3,2,1};//待排序的数组            
         int temp;//临时变量
         for (int i = 0; i < 9; i++)
         {
             for (int j = 9; j > i; j--)
                 if (a[j] < a[j - 1])//后面的值小于前面的，使前面的值总是小于后面的
                 {
                     //交换值
                     temp = a[j];
                     a[j] = a[j - 1];
                     a[j - 1] = temp;
                 }

         }
      //输出排序后的数组
          for(int i=0;i<10;i++)
          Console.Write(string.Format("{0},",a[i]));
        }
    }
}

（3）选择排序

选择排序第i次是选择数组中第i小的元素，并将该记录放到数组的第i个位置。换句话说，首先从未排序的序列中找到最小关键码，接着是次小的，依次类推，独特之处是很少交换。选择排序和冒泡排序比较相似，区别在于冒泡排序找到的最小元素是通过不断的交换相邻位置的值得到的，而选择排序只是先找到最新元素的位置，相当于数组的下标，然后最后一次交换。

View Code

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

namespace studyCSharp
{
    class Program
    {
        static void Main(string[] args)
        {
         int[] a={6,5,4,7,9,8,10,3,2,1};//待排序的数组            
         int temp;//临时变量
         for (int i = 0; i < 9; i++)
         {
             int minposition = i;
             for (int j = 9; j > i; j--)
                 if (a[j] < a[minposition])
                 {
                     minposition = j;//修改最小值的下标
                 }
             temp = a[i];
             a[i] = a[minposition];//将最小值赋值给a[i]
             a[minposition] = temp;
         }
      //输出排序后的数组
          for(int i=0;i<10;i++)
          Console.Write(string.Format("{0},",a[i]));
        }
    }
}

以上三种排序算法的平均时间复杂度均为：o（n*n）,关键的瓶颈在于只比较相邻的元素；因此比较和移动只能一步步进行（选择排序除外）

（4）二叉排序树

二叉排序树的特点：树中的任何一个节点，设其值关键码值为K，则该节点的左子树中任意一个节点的值都小于K；该节点右子树中任意一个节点的值都大于或等于K。如下图一个简单的二叉排序树所示：

根据二叉排序树的特点可知，中序遍历（左孩子-根节点-右孩子），可得到一个从小到大排好顺序的序列。查找某一个关键码为K的节点拥有折半查找的效率平均时间复杂度为：logn，二叉查找树中最关键的部分就是如何构造一个二叉排序树。下面代码实现一个二叉排序树的构造

View Code

#include<stdio.h>
#include<stdlib.h>
#define N 10
//申明节点的数据类型
    struct node{
        int item;
        struct node *leftchilid;
        struct node *rightchild;
    };
    typedef struct node Node;

    //定义向一棵书中插入节点的函数,构造一棵二叉查找树，Items参数为待插入的数组元素的首地址，root为树的根节点
    Node* AddNode(int Item, Node * root)
    {
        
        if(root==NULL)//为空树,直接将元素作为根节点
        {
         root=(Node*)malloc(sizeof(Node));
         root->item=Item;
         root->leftchilid=NULL;
         root->rightchild=NULL;
        }
        else
            if(Item<root->item)//添加到左子树中
                if(root->leftchilid==NULL)//左子树为空
                {
                        Node* newnode=(Node*)malloc(sizeof(Node));//直接分配动态内存给新的节点
                        newnode->item=Item;//将关键码值赋给新的节点
                        newnode->leftchilid=NULL;//初始化新的节点
                        newnode->rightchild=NULL;
                        root->leftchilid=newnode;//直接加到根节点的左子树中
                }
                else
                    AddNode(Item,root->leftchilid);//递归调用该左子树
            else //添加到右子树
                if(root->rightchild==NULL)//右子树为空
                {
                        Node* newnode=(Node*)malloc(sizeof(Node));//直接分配动态内存给新的节点
                        newnode->item=Item;//将关键码值赋给新的节点
                        newnode->leftchilid=NULL;//初始化新的节点
                        newnode->rightchild=NULL;
                        root->rightchild=newnode;//直接加到根节点的右子树中
                }
                else
                    AddNode(Item,root->rightchild);//递归调用该右子树，找到合适的地方加入新节点

        return root;
    }

    //中序遍历二叉排序树
    void midprint(Node* root)
    {
      if(root==NULL)//如果为空，直接返回
          return;
      midprint(root->leftchilid);//递归左孩子
      printf("%d,",root->item);
      midprint(root->rightchild);//递归右孩子    
    }

int main(void)
{    
        
    int a[N]={6,5,4,7,9,8,10,3,2,1};//待排序的数组
    Node* root=NULL;//定义树根
    root=(Node*)malloc(sizeof(Node));//将第一个元素当作树根
    root->item=a[0];
    root->leftchilid=NULL;
    root->rightchild=NULL;
    for(int i=1; i<N; i++)
    {
        AddNode(a[i],root);//循环插入剩下的节点    
    }
    midprint(root);//中序遍历，按顺序输出结果

    return 0;
}