常见排序算法（附C++代码实现） new

1.冒泡排序

冒泡排序遍历数组中的值，进行比较，并把最大的数值一道数组的顶端（就像气泡升到水面上）。

第一次迭代把数组最大的值移到数组顶端。

第二次迭代把第二大的值移到仅次于顶端的位置。

第三次迭代移动第三大值，以此类推。

view plaincopy to clipboardprint?
//冒泡排序
void BubbleSort(int array[],int n)
{
    for (int i = n-1;i>0;i--)
    {
        for (int j=0;j<=i;j++)
        {
            if (array[j] > array[j+1])
            {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }
}
//冒泡排序
void BubbleSort(int array[],int n)
{
for (int i = n-1;i>0;i--)
{
  for (int j=0;j<=i;j++)
  {
   if (array[j] > array[j+1])
   {
    int tmp = array[j];
    array[j] = array[j+1];
    array[j+1] = tmp;
   }
  }
}
}

2.选择排序

view plaincopy to clipboardprint?
//选择排序
void SelectSort(int array[],int n)
{
    for (int cur=0;cur<n;cur++)
    {
        for (int i=cur+1;i<n;i++)
        {
            if (array[cur]>array[i])
            {
                int tmp = array[cur];
                array[cur] = array[i];
                array[i] = tmp;
            }
        }
    }
}
//选择排序
void SelectSort(int array[],int n)
{
for (int cur=0;cur<n;cur++)
{
  for (int i=cur+1;i<n;i++)
  {
   if (array[cur]>array[i])
   {
    int tmp = array[cur];
    array[cur] = array[i];
    array[i] = tmp;
   }
  }
}
}

3.插入排序

view plaincopy to clipboardprint?
//插入排序
void InsertSort(int array[],int n)
{
    for (int i=1;i<n;i++)
    {
        int tmp = array[i];
        int pos = i-1;
        while ((pos>=0)&&(tmp<array[pos]))
        {
            array[pos+1] = array[pos];
            pos--;
        }
        array[pos+1] = tmp;
    }
}
//插入排序
void InsertSort(int array[],int n)
{
for (int i=1;i<n;i++)
{
  int tmp = array[i];
  int pos = i-1;
  while ((pos>=0)&&(tmp<array[pos]))
  {
   array[pos+1] = array[pos];
   pos--;
  }
  array[pos+1] = tmp;
}
}

4.快速排序

view plaincopy to clipboardprint?
//快速排序,left数组起始元素下标，right终止元素下标
void QuickSort(int array[],int left,int right)
{
    int mid,i,j;
    mid = array[(left+right)/2];
    i = left;
    j = right;
    do
    {
        while (array[i]<mid)
        {
            i++;
        }
        while(array[j]>mid)
        {
            j--;
        }

        if (i<=j)
        {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            i++;
            j--;
        }
    } while (i<=j);

    if (left < j)    //当左边部分有值(left<j)，递归左半边
    {
        QuickSort(array,left,j);
    }

    if (right > i)   //当右边部分有值(right>i)，递归右半边
    {
        QuickSort(array,i,right);
    }
}
//快速排序,left数组起始元素下标，right终止元素下标
void QuickSort(int array[],int left,int right)
{
int mid,i,j;
mid = array[(left+right)/2];
i = left;
j = right;
do
{
  while (array[i]<mid)
  {
   i++;
  }
  while(array[j]>mid)
  {
   j--;
  }

  if (i<=j)
  {
   int tmp = array[i];
   array[i] = array[j];
   array[j] = tmp;
   i++;
   j--;
  }
} while (i<=j);

if (left < j) //当左边部分有值(left<j)，递归左半边
{
QuickSort(array,left,j);
}

if (right > i) //当右边部分有值(right>i)，递归右半边
{
QuickSort(array,i,right);
}
}

5.希尔排序

view plaincopy to clipboardprint?
//希尔shell排序
void ShellSort(int array[] , int n)
{
    int iStep,i,j;
    for (iStep=n/2;iStep>0;iStep/=2)
    {
        for (i=iStep;i<n;i++)
        {
            for (j=i-iStep;j>0;j-=iStep)
            {
                if (array[j] > array[j+iStep])
                {
                    int tmp = array[j];
                    array[j] = array[j+iStep];
                    array[j+iStep] = array[j];
                }
            }
        }
    }
}
//希尔shell排序
void ShellSort(int array[] , int n)
{
int iStep,i,j;
for (iStep=n/2;iStep>0;iStep/=2)
{
  for (i=iStep;i<n;i++)
  {
   for (j=i-iStep;j>0;j-=iStep)
   {
    if (array[j] > array[j+iStep])
    {
     int tmp = array[j];
     array[j] = array[j+iStep];
     array[j+iStep] = tmp;
    }
   }
  }
}
}

参考资料：

http://blog.chinaunix.net/u/1222/showart_318070.html

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/massice/archive/2010/06/20/5681941.aspx

秒客网

常见排序算法（附C++代码实现） new

相关文章