7中排序算法

冒泡排序：最简单的一种排序算法。先从数组中找到最大值(或最小值)并放到数组最左端(或最右端)，然后在剩下的数字中找到次大值(或次小值)，

以此类推，直到数组有序排列。算法的时间复杂度为O(n^2)。

for (int i=0;i<10;i++)

    {

        for (int j=i+1;j<10;j++)

        {

            if (a[i]>a[j])

            {

                temp = a[j];

                a[j] = a[i];

                a[i] = temp;

            }

        }

    }

    

for (int i=0;i<10;i++)

    {

        for (int j=9;j>=i+1;j--)

        {

            if (a[j-1]>a[j])

            {

                temp = a[j];

                a[j] = a[j-1];

                a[j-1] = temp;

            }

        }

    }

 

第二种应该是正统的，符合那个逻辑流程的冒泡排序

 

2、选择排序

 

严蔚敏版《数据结构》中对选择排序的基本思想描述为：每一趟在n-i+1(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。

具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，

则将最小值min1和arr[0]交换，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。

算法的时间复杂度为O(n^2)。

 

int  a[10] = { 5,6,9,8,9,6,3,5,1,3 };

    int temp = -1;

    int index = 0;

    for (int i=0;i<10;i++)

    {

        index = i;

        temp = a[i];//每次进入排序的时候，假设自己为最小的

        for (int j=i+1;j<10;j++)

        {

            if (temp>a[j])

            {

                index = j;//如果发现自己不是最小的，那么就记录这个值，和下标的值

                temp = a[j];

            }

        }

        a[index] = a[i];

        a[i] = temp;//互相交换值

    }

    for (int i=0;i<10;i++)

    {

        cout << a[i] << " ";

    }

    

3.插入排序的基本思想就是将无序序列插入到有序序列中。例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列(图中用蓝色标出)，

将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，无序序列变成了[8,0,5,1]。无序序列中8比4大

，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

 

这是我初步写的，算是半成品的插入排序吧，

for (int i=1;i<10;i++)//新插入的i下标

    {

        for (int j=0;j<i;j++)//已经拍好序的部分，初始是第一位0假设排好序了

        {

            if (a[i]<a[j])

            {

                temp = a[j];

                a[j] = a[i];

                a[i] = temp;

            }

        }

        for (int i = 0; i < 10; i++)

        {

            cout << a[i] << " ";

        }

        printf("\n");

    }

    

下面这个才是符合插入排序逻辑的插入排序：    

int  a[10] = { 8,9,6,3,5,7,1,2,4,0};

    int temp = -1;

    int index = 0;

    for (int i=1;i<10;i++)

    {

        temp = a[i];//要插入的数

        for (index =i-1; index >=0; index--)

        {

            if (temp<a[index])

            {

                a[index + 1] = a[index];

            }

            else

            {

                break;

            }

            for (int i = 0; i < 10; i++)

            {

                cout << a[i] << " ";

            }

            printf("\n");

        }

        a[index + 1] = temp;

    }

    for (int i = 0; i < 10; i++)

    {

        cout << a[i] << " ";

    }

    printf("\n");

 

//下面这种是改进的插入排序，具体的实现细节差别不大

int a[10]={6,5,4,3,2,1,0,9,8,7};

    int temp,index;

    for (int i=1; i<10; i++)

    {

        if (a[i]<a[i-1])//说明出现需要调换的情况，因为是升序排序，这里已经假设第一个数字已经排好序了

        {

            temp=a[i];

            for ( index=i-1; index>=0; index--)

            {

                if (temp<a[index])//只要a还继续比前面的数字小，那么久应该继续的换下去

                {

                    a[index+1]=a[index];

                }

                else

                    break;

            }

            a[index+1]=temp;

        }

    }

 

 4.希尔排序

　　希尔排序在插入排序的算法的基础上进行了改进，算法的时间复杂度与前面几种算法相比有较大的改进。其算法的基本思想是：先将待排序记录序列分割成若干个子序列进行分别插入排序，等待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

 

　

/*===========================下面这段代码，又是失败的希尔排序，gap并没有分配好，事实上，这个gap应该是呈等差数列往右顺序下去的，但是我这部分没做好=============*/　

//这段是插入排序

void insertSort(int a[],int b)

{

    int temp=0;

    int index=0;

    for (int i=1; i<b; i++)

    {

        temp=a[i];

        for ( index=i-1; index>=0; index--)

        {

            if (temp<a[index])

            {

                a[index+1]=a[index];

            }

            else

            {

                

                break;

            }

        }

        a[index+1]=temp;

    }

}

//把插入排序当作函数调用m，分别对需要排序的数组按照一定的规则进行拆分m，这些子部分分别进行插入排序

//就实现了所谓的希尔排序、

int main()

{

    int a[10]={6,5,4,3,2,1,0,9,8,7};

    //insertSort(&a[0], 10);

    int temp=0;

    int index=0;

    int gap=10;

    for ( gap=gap/3+1; gap>=1; gap=gap/3+1)//制造一个gap

    {

        for (int i=gap; i<10; i+=1)//每个不同的gap中，分别执行插入排序

        {

            temp=a[i];

            for ( index=i-gap; index>=0; index-=gap)

            {

                if (temp<a[index])

                {

                    a[index+gap]=a[index];

                }

                else

                {

                    

                    break;

                }

            }

            a[index+gap]=temp;

        }

        if (gap==1)//防止出现死循环，执行过一次gap=1的情况就行了

        {

            break;

        }

    }

    

    for (int i=0; i<10; i++) {

        cout<<a[i]<<" ";

    }

    printf("\n");

    return 0;

}

/*===============================这部分是正确的逻辑写的==========================按照逻辑从新再写一遍，这次应该不会出错了。================*/

 

 勉强实现了希尔排序，逻辑处理部分做的不好，下次回头来重新再写希尔排序的时候，我再重新优化下逻辑，给出优化的代码。

 

for (gap=10/3+1; gap>=1; gap=gap/3+1)//制造出很多种gap，来实现希尔排序和插入排序的主要区别所在

    {

        for (int i=0; i<gap; i++)//是从0到gap之间的数字（分为那么多组）作为第一个数字开始，逐步的往上加gap的值，直到最大长度停止

        {

            for (index=i+gap; index<10; index+=gap)

            {

                

                int k;

                if (a[index]<a[index-gap])//说明需要进行插入排序

                {

                    temp=a[index];

                    for (k=index-gap; k>=0; k-=gap)//这里的gap是关键，实现了较大的数字逐渐往后移的这么一个动作

                    {

                        if (temp<a[k])

                        {

                            a[k+gap]=a[k];

                        }

                        else

                            break;

                    }//结束了---》存在2种情况：1.k<0了，于是k+gap的那个位置的值应该是属于temp的

                    //2.break了，

                    a[k+gap]=temp;

                }

                

            }

        }

        if(gap==1)//只执行一次的gap=1的情况

            break;

    }

 

 

5、快速排序 快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。 一趟快速排序的具体做法为：设置两个指针low和high分别指向待排序列的开始和结尾，记录下基准值base val(待排序列的第一个记录)，然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换，接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换，重复这两个步骤直到low=high为止。

 

void QuickSort(int v[], int left, int right)

{

    if (left<right)//套在最外层，防止死循环，递归调用

    {

        int key=v[left];//记录了初始第一个传进来的left的值

        int low=left,high=right;

        while (low<high)//管理左边和右边能否继续循环下去的关键

        {

            while (low<high) {

                if (v[high]<key)

                {

                    v[low]=v[high];//此时m，low下标下的值被改变了，此时v[low]的值被保存在key中，假设low=left=0=第一次传进来的值，

                    break;

                }

                high--;//从末尾向左移动

            }

            while (low<high)

            {

                if(v[low]>key)

                {

                    v[high]=v[low];//此时的high的下标位置，是上面v[high]赋值给v[low]，空下的m，可以占用的下标。

                    break;

                }

                low++;//从y最左边向右移动

            }

            

        }

        v[low]=key;//这个v[low]是上面v[low]赋值给v[high]，空下的，可以占用的下标。第一次low=0的下标保存的值，key被返回到剩下的位置中了

        QuickSort(v, left, low-1);

        QuickSort(v, high-1, right);

        //上面这2个递归调用的中间段m，low-1 high+1 特别重要，如果忘记写了，会造成递归调用无法停止，使得程序出错

        //此时的值low=high

    }

    

}

int main()

{

    //int a[10]={6,5,4,3,2,1,0,9,8,7};

    int a[2]={3,2};

    // 快速排序

    QuickSort(&a[0], 0, 1);

   

    

    for (int i=0; i<2; i++) {

        cout<<a[i]<<" ";

    }

    printf("\n");

    return 0;

}