交换排序

交换排序：根据序列中俩个元素关键字的比较结果来对换这两个记录在序列中的位置。

1.冒泡排序

定义：从后往前（或从前往后）俩俩比较相邻元素的值，若为逆序（即arr[i-1] > arr[i]），则交换它们，直到序列比较完成。称这样的过程为“一趟”冒泡排序。
代码实现:

  /**
    冒泡排序
    空间复杂度：O(1)
    最好情况（有序）：O(n)
    最坏情况（逆序）：O(n^2)
    平均时间复杂度：O(n^2)
    稳定性：稳定
    对链表进行排序：是
*/
void MyBubbleSort(int arr[], int n){
    int temp;   // 定义暂存变量
    int flag;   // 如果一趟没有发生交换则直接退出循环
    for(int i=0; i<n-1; i++){
        flag = 0;
        for(int j=n-1;j>i;j--){
            if(arr[j-1] > arr[j]){
                temp = arr[j-1];    // 交换俩者
                arr[j-1] = arr[j];
                arr[j] = temp;
                flag = 1;
            }
        }
        if(flag == 0){
            return;
        }
    }
}

2.快速排序

算法思想：在待排序表L[1...n]中任取一个元素作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的俩部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]中所有元素小于基准，L[k+1...n]中所有元素大于等于基准，则基准元素放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归的对俩个子表重复上述过程，直至没部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
每一层的递归调用只需要处理剩余的待排序元素，时间复杂度不超过O(n)

• 1.时间复杂度=O(n*递归层数)
  最好时间复杂度=O(n(lnn/ln2))
  最坏时间复杂度=O(n^2)
  平均时间复杂度=O(n(lnn/ln2))
  快速排序是所有内部排序算法中平均性能最优的排序算法
• 2.空间复杂度=O(递归层数)——主要是递归工作栈
  最好空间复杂度=O((lnn/ln2))
  最坏空间复杂度=O(n)
• 3.若初始序列有序或逆序，则快速排序的性能最差(因为每次选择的都是最靠边的元素)
• 4.尽量选择可以把数据中风的基准元素
  A：选头，中，尾三个位置的元素，取中间值作为枢轴元素；
  B：随机选择一个元素作为基准
• 5.稳定性：不稳定

代码实现：

 // 快速排序
void QuickSort(int arr[], int low, int high){
    if(low < high){
        int pivotPosition = SeparateParts(arr, low, high);  // 划分
        QuickSort(arr, low, pivotPosition-1);   // 划分左子表
        QuickSort(arr, pivotPosition+1, high);  // 划分右子表
    }
}

// 用第一个元素将待排序列划分成左右俩个部分
int SeparateParts(int arr[], int low, int high){
    int pivot = arr[low]; // 数组的第一个元素作为基准
    while(low < high){
        while(low<high && arr[high]>=pivot)
            --high;
        arr[low] = arr[high];   // 比基准小的元素移动到左端
        while(low<high && arr[low]<=pivot)
            ++low;
        arr[high] = arr[low];   // 比基准大的元素移动到右端
    }
    arr[low] = pivot;   // 基准元素存放到最终位置
    return low; // 返回存放基准的最终位置
}

3.总结

通过对俩种交换排序的算法学习，使自己的思维得到了显著的提升，继续加油继续进步。