记录一些学习小事

Work hard

统计

留言簿

阅读排行榜

评论排行榜

总结的几个排序算法

快速排序:
思想 一个标记数(取数组最后一个数)  左边放比他小的所有数 右边放比它都大的数
这样分成的两个数组 在进行 尾部一个数作为标记数作为标记分割数组
一直到分不了为止  自然就排好了续   用具体数字分析一下
一个数组char data[9]={2,5,8,3,7,6,1,9,4};
分开这个数组 看好了怎么把比4小的数都放到它前边
 int biaoji=data[8];//最后一个数
 int weizhi=data[j];//这个一个位置数 一开始把它放在最前边 j会++
 data[i];//这个是用来遍历数组的。i会++
for(int i=0;i<8;i++)//因为最后一个数是标记 所以只要对前8个数进行遍历就行
{
 if(data[i]<biaoji)
 {
   交换data[i]和weizhi
   位置的j++ 位置向后走一位(这个位置就意味着比标记小的数都放到位置的左边边) 
 }
}
在分开之后 我们要把我们的标记(也就是最后一个数)和我们的位置数 换一下
这样就做到了这样的事 把{2,5,8,3,7,6,1,9,4} 换成了{2,3,1,4,7,6,8,9}
好了 上代码 在看看代码相信 就都会了。
这是我用c++实现的代码 哈哈写完了感觉很爽!

#include <iostream>
using namespace std;
//得到分割点 把小于最后一个数的数放在i前边
//iData 是数组{2,5,8,3,7,6,1,9,4} iBegin是开始的索引0  iEnd是结束的索引8
int getCutpoint(int * iData,int iBegin,int iEnd)
{
  int iCut=iData[iEnd];
  int i=iBegin;
 int temp;
  for(int j=iBegin;j<iEnd;j++)
  {
   //如果前面的比最后一个iCut小的话,那么让
   //iData[i]和iData[j]换
   if (iData[j]<=iCut)
   {
    temp=iData[i];
    iData[i]=iData[j];
    iData[j]=temp; 
    i++;
  }
  }
  //交换最后一个与i处也就是cut处
  iData[iEnd]=iData[i];
  iData[i]=iCut;
 return i;//返回分割的索引
}
void fastSortCallBack(int * iData,int iBegin,int iEnd)
{
 if (iBegin>=iEnd)
 {
  return;
 }
 int i=getCutpoint(iData,iBegin,iEnd);
 //回调继续getcutpoint左部分
 fastSortCallBack(iData,iBegin,i-1);
 //回调继续getcutpoint右部分
 fastSortCallBack(iData,i+1,iEnd);
 return ;
}
void fastSort(int * iData,int iLength)
{
 fastSortCallBack(iData,0,iLength-1);
}
int main()
{
 int d[9]={2,5,8,3,7,6,1,9,4};
 fastSort(d,9);
 for (int i=0;i<9;i++)
 {
  cout<<d[i]<<" ";
 }
 system("pause");
 return 0;
}

 


选择排序:
选择排序和冒泡排序思路上有一点相似,都是先确定最小元素,再确定第二笑元素,最后确定最大元素。这个方法比较简单,他的主要流程如下:
1.加入一个数组A = {5,3,6,2,4,7},我们对他进行排序
2.确定最小的元素放在A[0]位置,我们怎么确定呢,首先默认最小元素为5,他的索引为0,然后用它跟3比较,比他打,则认为最小元素为3,他的索引为1,然后用3跟6比,发现比他小,最小元素还是3,然后跟2比,最小元素变成了2,索引为3,然后跟4比,跟7比。当比较结束之后,最小元素也尘埃落定了。就是2,索引为3,然后我们把他放在A[0]处。为了使A[0]原有数据部丢失,我们使A[0](要放的位置) 与A[3](最小数据的位置)交换。这样就不可以了吗?
3.然后我们在来找第二小元素,放在A[1],第三小元素,放在A[2]。。当寻找完毕,我们排序也就结束了。
4.不过,在找的时候要注意其实位置,不能在找A[2]的时候,还用A[2]的数据跟已经排好的A[0],A[1]比,一定要跟还没有确定位置的元素比。还有一个技巧就是我们不能每次都存元素值和索引,我们只存索引就可以了,通过索引就能找到元素了。呵呵。
5.他和冒泡的相似和区别,冒泡和他最大的区别是他发现比他小就交换,把小的放上面,而选择是选择到最小的在直接放在确定的位置。选择也是稳定的排序  ,这个还是很好实现的。

void SelectSort(int* pnData, int nLen)
{
    //i从[0,nLen-1)开始选择,确定第i个元素
    for (int i = 0; i < nLen - 1; ++i)
    {
        int nIndex = i;
        //遍历剩余数据,选择出当前最小的数据
        for (int j = i + 1; j < nLen; ++j)
        {
            if (pnData[j] < pnData[nIndex])   
            {
                nIndex = j;
            }
        }
        //如果当前最小数据索引不是i,也就是说排在i位置的数据在nIndex处
        if (nIndex != i)       
        {
            //交换数据,确定i位置的数据。
            int nTemp = pnData[i];
            pnData[i] = pnData[nIndex];
            pnData[nIndex] = nTemp;
        }
    }
}

 


插入排序:
思想,从第二个元素开始向后遍历,然后跟前面比较,如果比前边的元素小则向前插入
由data[1]和data[0]比较 如果data[1]<data[0]则data[0]后移一位 然后data[1]插入到data[0]位置
当然了,在data[0]后移的时候要用temp 记录data[1]的值
这样继续下去……
if(data[i]<(data i 前边的元素))
{
  data i 前边的元素就后移
}
最后把data[i]放到该插入的地方去 下面献上一点点代码 其中主要不好弄的是在头部
比如{3,4,5,6,2,1} 这个2 和 1 向前插入的话2 比第一个数3还要小 所以他下一步就要去
和索引为-1的数比较,这是不允许的。所以……如下
void insertSort(int * pData,int iLength)
{
 //从第二个元素开始 向前插
 int temp=pData[1];
 for (int i=1;i<iLength;)
 {
  for (int j=i-1;j>=0;j--)
  {
   //如果temp比前边的大,则前边的后移 最后把temp放在前面
   if (temp<pData[j])
   {
    pData[j+1]=pData[j];
     if (j==0)
     {
      pData[0]=temp;
     } 
   }
    else
    {
     pData[j+1]=temp;
     break;
    }
   
  }
  
  temp=pData[++i];
 }
}

 

 

希尔排序

待学习。

 


堆排序!!!!!!!!!!

 还不会呢。。

 

冒泡排序  略……

posted on 2011-07-30 14:29 陈晓 阅读(281) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理