数据结构 冒泡排序 选择排序 学习笔记

数据结构 冒泡排序 选择排序 学习笔记

首先我们了解一下冒泡排序

摘录自

原文链接：

其原理是依次把数组中相邻两个数比较大小来决定是否换顺序，从而把最大（小）的数字排在最前（后）的方法。

例如：假设一维数组arr[5]={1,4,2,5,0]，那么冒泡排序法原理为（其中一种方式）：

1＜4，不交换顺序。
4＞2，交换顺序，arr[5]={1,2,4,5,0}.
4＜5，不交换顺序。
5＞0，交换顺序，arr[5]={1,2,4,0,5}.
最大数字已经排在第5位，下面从第一位开始排序到第四位截止：
1＜2，不交换顺序。
2＜4，不交换顺序。
4＞0，交换顺序，arr[5]={1,2,0,4,5}.
第二大数字排在第四位，下面从第一位开始排序到第三位截止。。。以此类推，直到循环结束。
 

这里我们对传统的冒泡排序进行了优化

1.

首先 在我们遍历完一次后   找出最后一个是最大的  

再次遍历找倒数第二个元素时  就不用和最后一个比较

以此类推 

for (int i = 0; i < nLen - 1; i = nLen - 1 - Flag )
        {
            

            for (int j = 0; j < nLen - 1 - i; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                    Flag = j;
                }
                ncount++;
            }

此处第二个for循环  j的判断条件可以改为j < nLen - 1 - i

2.其次  我们在第一个for循环的条件

for (int i = 0; i < nLen - 1; i = nLen - 1 - Flag )

i = nLen - 1 - Flag可以减少遍历次数 

我们在遍历时  i视为nLen - 1 - Flag

其中 Flag是最后一次交换的元素的下标;

冒泡排序完整代码如下

#include<iostream>
using namespace std;
void BubbleSort(int arr[],int nLen)
{if (arr == NULL || nLen <= 1){return;}int ncount = 0;int Flag = 0;for (int i = 0; i < nLen - 1; i = nLen - 1 - Flag ){for (int j = 0; j < nLen - 1 - i; j++){if (arr[j] > arr[j + 1]){arr[j] = arr[j] ^ arr[j + 1];arr[j + 1] = arr[j] ^ arr[j + 1];arr[j] = arr[j] ^ arr[j + 1];Flag = j;}ncount++;}if (Flag == 0){break;}/*else{i = nLen - 1 - Flag-1;}*/}cout << ncount << endl;
}int main()
{int arr[10] = { 3,2,1,5,3,6,8,9,7,8 };BubbleSort(arr, 10);/*for (int val =0;val<10;val++){cout << arr[val] << endl;}*/for  (int val:arr){cout << val << " ";}return 0;
}

 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

完整代码如下

#include<iostream>
using namespace std;
void SelectSort(int arr[], int nLen)
{if (arr == NULL || nLen <= 1){return;}for (int i = 0; i < nLen - 1; i++){int mark = i;for (int j = i; j < nLen ; j++){if (arr[j]<arr[mark]){mark = j;}}if ( mark!=i){arr[i] = arr[i] ^ arr[mark];arr[mark] = arr[i] ^ arr[mark];arr[i] = arr[i] ^ arr[mark];}}}int main()
{int arr[10] = { 0,2,1,5,3,6,8,9,7,8 };SelectSort(arr, 10);for  (int val:arr){cout << val << " ";}return 0;
}