内部排序算法总结-第二篇

这篇接着介绍排序算法——交换排序

一、冒泡排序

1、冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

　　2、算法描述：

比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。

代码

方法一：

void bubblesort(int arr[], int n)
{
    for (int  i = 0; i < n-1; i++)
    {
        //表示本趟冒泡是否发生交换的标志
        bool flag = false;
        //一趟冒泡过程
        for (int j = n - 1; j > i;j--)
        {
            //若为逆序，交换
            if (arr[j-1]>arr[j])
            {
                swap(arr[j - 1], arr[j]);
                flag = true;
            }
        }
        //本趟遍历后没有发生交换，说明表已经有序
        if (flag==false)
        {
            return;
        }
    }
}

View Code

二、代码实现

C ：

#include<iostream>
using namespace std;

void swap1(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

void swap2(int &left, int &right)
{
    int temp = left;
    left = right;
    right = left;
}

void swap3(int &left, int &right)
{
    if (&left != &right)
    {
        left ^= right;
        right ^= left;
        left ^= right;
    }
}


void BubbleSort1(int arr[], int num)
{
    int i, j;
    for (i = 0; i < num; i++)
    {
        for (j = 1; j < num - i; j++)
        {
            if (arr[j - 1] > arr[j])
                swap1(&arr[j - 1], &arr[j]);
        }
    }
}


void BubbleSort2(int arr[], int num)
{
    int k = num;
    int j;
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = true;
            }
        }
        k--;
    }
}

void BubbleSort3(int arr[], int num)
{
    int k, j;
    int flag = num;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap1(&arr[j - 1], &arr[j]);
                flag = j;
            }
        }
    }
}


int main(void)
{
    int arr[] = { 9, 2, 5, 8, 3, 4, 7, 1, 6, 10 };
    BubbleSort1(arr, 10);
    for (int i = 0; i < 10; i++)
        cout << arr[i] << ' ';
    cout << endl;
    system("pause");
    return 0;
}

View Code

python：

import numpy as np
def bubbleSort(alist):
    for passnum in range(0, len(alist) - 1, 1):
        for i in range(0, len(alist) - passnum - 1, 1):
            if (alist[i] > alist[i + 1]):
                tmp = alist[i + 1]
                alist[i + 1] = alist[i]
                alist[i] = tmp

alist = np.random.randint(1,100,10)
bubbleSort(alist)
print(alist)

View Code