普通排序算法(插入、交换、冒泡)

全部于VC6.0下编译通过。

1、插入排序: 将数组第一个元素看做有序，然后每次将有序序列的后一个无序元素（即无序序列的第一个元素）插入到前面有序序列的正确位置，使之保持有序，直至无序序列为空。

#include<iostream>
using namespace std;
template <class T>
void InsertSort(T list[],int n) //插入排序

{
    if(n<2) return;
    for(int i=1; i<n; i++)
        for(int j=i-1; j>=0; j--)
            if(list[j] > list[j+1])
            {
                list[j]=list[j]^list[j+1];
                list[j+1]=list[j]^list[j+1];
                list[j]=list[j]^list[j+1];
            }
}

void main()
{
    int list[10]={10,5,6,9,8,1,7,3,2,4};
    InsertSort(list,10);
    cout<<"排序后得到：";
    for(int i=0; i<10; i++)
        cout<<list[i]<<' ';
    cout<<endl;
}

 

2、选择排序: 开始将整个序列看做无序，第1趟找出n中最小的元素与第1个元素（list[0]）交换，此时无序序列元素剩下n-1个，第2趟找出无需序列n-1中最小元素与第2个元素（list[1]）交换，…，以此类推直至n-1趟（与（list[n-2]）的交换，剩下最后一个元素list[n-1]必有序）。

#include<iostream>
using namespace std;
template <class T>
void SelectionSort(T list[], int n) //选择排序

{
    if(n<2) return;
    for(int i=0,j,least; i<n-1; i++) //当前面都有序，最后一个即下标为n的元素为有序。

    {
        for(j=i+1,least=i; j<n; j++)
            if(list[j] < list[least])
                least=j;
        if(least > i)
        {
            list[i]=list[i]^list[least];
            list[least]=list[i]^list[least];
            list[i]=list[i]^list[least];
        }
    }
}

void main()
{
    int list[10]={10,5,6,9,8,1,7,3,2,4};
    SelectionSort(list,10);
    cout<<"排序后得到：";
    for(int i=0; i<10; i++)
        cout<<list[i]<<' ';
    cout<<endl;
}

 

3、冒泡排序: 一次次遍历（一共遍历n-1次）,每次找出最小的往数组前面移动。

#include<iostream>
using namespace std;
template <class T>
void BubbleSort(T list[], int n) //冒泡排序

{
    if(n<2) return;
    for(int i=0; i<n-1; i++)
        for(int j=n-1; j>i; j--)
            if(list[j] < list[j-1])
            {
                list[j]=list[j]^list[j-1];
                list[j-1]=list[j]^list[j-1];
                list[j]=list[j]^list[j-1];
            }
}

void main()
{
    int list[10]={10,5,6,9,8,1,7,3,2,4};
    BubbleSort(list,10);
    cout<<"排序后得到：";
    for(int i=0; i<10; i++)
        cout<<list[i]<<' ';
    cout<<endl;
}