数据结构实验-折半插入排序-双向冒泡排序

本是古典何须时尚 2024-03-31 01:26 26阅读 0赞

**目录**

分析：

折半插入排序

双向冒泡排序

折半插入排序

思想：

代码

运行结果

双向冒泡排序

代码

运行结果

--------------------

### 分析： ###

*  #### 折半插入排序 ####

折半插入排序，折半插入排序是在直接插入的改进，通过折半查找得到插入位置，减少比较次数。

折半插入排序的基本思想是：设在数据表中有一个元素序列a\[0\],a\[1\],……,a\[n-1\]。其中，a\[0\],a\[1\],……,a\[i-1\]已经排好序。在插入a\[1\]时，利用折半查找法寻找a\[i\]的插入位置。

*  #### 双向冒泡排序 ####

**传统冒泡算法原理**

**·冒泡排序算法的运作如下：（从后往前）**

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

**双向冒泡算法原理**

**·双向冒泡排序算法的运作如下：**

1.  传统冒泡气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作
2.  使用left与right两个旗标来记录左右两端已排序的元素位置。

一个排序的例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 \[81\]

向左排序：\[11\] 19 45 77 13 28 18 19 77 \[81\]

往右排序：\[11\] 19 45 13 28 18 19 \[77 77 81\]

向左排序：\[11 13\] 19 45 18 28 19 \[77 77 81\]

往右排序：\[11 13\] 19 18 28 19 \[45 77 77 81\]

向左排序：\[11 13 18\] 19 19 28 \[45 77 77 81\]

往右排序：\[11 13 18\] 19 19 \[28 45 77 77 81\]

向左排序：\[11 13 18 19 19\] \[28 45 77 77 81\]

如上所示，括号中表示左右两边已排序完成的部份，当left >= right时，则排序完成。

--------------------

### 折半插入排序 ###

*  #### 思想： ####

1.  在排序第i个数时，前i-1个数已经排序完成，这是折中排序的前提，所以在开始排序时起始位置为i=1
2.  折中排序，顾名思义就是折中，所以在折中排序时，先要以谁开头以谁结尾，所以需要定义两个变量front，end，有了这两个变量才能够找到他们的中间值mid
3.  排序的最终目的还是找到i的最终插入位置，本代码要求升序排序，所以只需找到比下标为i的数小的数的下标
4.  以此时只需将mid的值与i的值作比较，如果arr\[i\]<arr\[mid\]的话，此时说明下标为i的插入位置为\[0,mid-1\]所以end的位置，应该为mid-1，依次类推，反之则front的位置为mid+1
5.  当front值大于end值的时候则此时说明找到了下标为i的数的插入位置，位置为front
6.  找到插入位置后只需将i-1到front的数向后移动一位，则此时front的位置空出来之后，将下标为i的值插入就完成了排序

*  #### 代码 ####

#include<iostream>
    using namespace std;
    
    void binaryInsertSort(int a[],int len) {
    	int front, end,temp;
    	for (int i = 1; i < len; i++) {
    		temp = a[i];
    		front = 0;
    		end = i - 1;
    		while (front<=end)
    		{
    			int mid;
    			mid = (front + end) / 2;
    			if (temp < a[mid]) {
    				end = mid - 1;
    			}
    			else {
    				front = mid + 1;
    			}
    		}
    		for (int j = i; j > front; j--) {
    			a[j] = a[j - 1];
    		}
    		a[front] = temp;
    	}
    	//排序
    	cout << "从小到大排序为：";
    	for (int k = 0; k < len; k++) {
    		cout << a[k] << "\t";
    	}
    	cout << endl;
    }
    int main() {
    	int arr[10];
    	cout << "请输入10个数：" << endl;
    	for (int i = 0; i < 10; i++) {
    		cin >> arr[i];
    	}
    
    	cout << "这10个数为：";
    	for (int i = 0; i < 10;i++) {
    		cout << arr[i] << "\t";
    	}
    	cout << endl;
    
    	//折半排序
    	binaryInsertSort(arr,10);
    	system("pause");
    	return 0;
    }

*  #### 运行结果 ####

![8c8231d6f5164916a96bc9cad2055fef.png][]

--------------------

### 双向冒泡排序 ###

*  #### 代码 ####

#include <iostream>
    using namespace std;
    
    void bubbleSort(int a[], int n) {
        int left = 0, right = n - 1;
        while (left < right) {
            int flag = 0;
            // 从左到右选最大的值
            for (int j = left; j < right; ++j) {
                if (a[j] > a[j + 1]) {
                    swap(a[j], a[j + 1]);
                    flag = 1;
                }
            }
            // 从右到左选最小的值
            --right;
            for (int m = right; m > left; --m) {
                if (a[m] < a[m - 1]) {
                    swap(a[m], a[m - 1]);
                    flag = 1;
                }
            }
            ++left;
            if (!flag) {
                break;
            }
        }
        cout << "双向冒泡排序为：";
        for (int i = 0; i < n;i++) {
            cout << a[i] << "\t";
        }
        cout << endl;
    }
    
    int main() {
    
        int arr[] = { 8, -1, 0, 6, -2, 1, 7, 9, 0, 2, 5, 4, 3 };
        int len = sizeof(arr) / sizeof(arr[0]);
    
        cout << "这组数为：\t";
        for (int i = 0; i < len; i++) {
            cout << arr[i] << "\t";
        }
        cout << endl;
        cout << endl;
        //双向冒泡排序
        bubbleSort(arr, len);
        /*for (const int& temp : arr) {
            cout << temp << " ";
        }*/
        cout << endl;
        return 0;
    }

*  #### 运行结果 ####

![39c50dfbc8144d99914df1e313037377.png][]

[8c8231d6f5164916a96bc9cad2055fef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c71dd68550c649f886bd992315e0ed59.png
[39c50dfbc8144d99914df1e313037377.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/749963a9b46c46ca931e2811a9d580fa.png