交换类排序

3）冒泡排序

https://www.bilibili.com/video/BV1hg411V7Bm/?p=69

冒泡排序的基本思想是：通过相邻元素之间的比较和交换，将排序码较小的元素主键从底部移向顶部。

由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。

void bubbleSort(int arr[], int n)
{
    int temp;
    int i,j;
    for(i=0; i<n-1;i++) //外循环为排序趟数，n个数进行n-1趟
    {
       for(j=0;j<n-1-i;j++) //内循环为每趟比较的次数，第i趟比较n-i次
       {
           if (arr[j]>arr[j+1]){ //相邻元素比较，若逆序则交换
               temp=arr[j];
               arr[j]=arr[j+1];
               arr[j+1]=temp;
           }
       }//end inner for
    }//end outter for
}

4）快速排序

快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。

通过递归解决这些子问题，然后再将这些子问题的解组合成原问题的解。

快速排序通常包括两个步骤：

第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。

第二步，采用相同的方法对左、右两组分别进行排序，知道所有记录都排到响应的位置为止。

void quickSort() //快速排序
{
    int i,j;
    int pivot=a[0]; //设置基准值
    i=0;
    j=n-1;
    while(i<j)
    {
        while(i<j&& a[j]>pivot){ //大于基准值者保持在原位置
            j--;
        } 
        if(i<j){
            a[i]=a[j];
            i++;
        }
        while(i<j&&a[i]<=pivot) { //不大于基准值保持在原位置
            i++;
        }; 
        if(i<j)
        {
             a[j]=a[i];
             j--;
        }
    }//end while
    a[i]=pivot; //基准元素归位
    if(i>1) quickSort(a, i); //递归地对左子序列进行快速排序
    if(n-i-1>1) quickSort(a+i+1, n-i-1); //递归地对右子序列进行快速排序
}

考点：一趟排序结果比较

采用（）算法对序列{18，12，10，11，23，2，7}进行一趟递增排序后，其元素的排列变为{12，10，11，18，2，7，23}。

A、选择排序

B、快速排序

C、归并排序

D、冒泡排序 √

解：

最大的是23,23一趟下来到最后了，冒泡一趟下来能把最大的数排到最后

假如是冒泡：

1趟1次比：18>12，交换

12，18，10，11，23，2，7

1趟2次比：18>10，交换

12，10，18，11，23，2，7

1趟3次比：18>11，交换

12，10，11，18，23，2，7

1趟4次比：18<23，不变

1趟5次比：23>2，交换

12，10，11，18，2，23，7

1趟6次比：23>7，交换

12，10，11，18，2，7，23