冒泡与快速排序

发表于 更新于 分类于 阅读次数：
用 C# 实现冒泡排序与快速排序算法，附完整代码示例与运行文字说明，适合算法初学者理解排序思想与时间复杂度对比。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * 冒泡排序：比较相邻的前后二个数据，如果前面数据大于（小于）后面的数据，就将二个数据交换，循环n-1次
 */
private void BubbleSort()
{
    //定义数组
    int[] arr = {80,10,5,40,60,1,20,10};

    //临时存储
    int temp;

    //外循环：从数组第一个值循环到倒数第二个值
    for (int i = 0; i < arr.Length-1; i++)
    {
        //内循环：把最大数字的排在后面
        //比较的总是比i大的值，前面的值已经冒泡完成了
        for (int j = i+1; j < arr.Length; j++)
        {
            //前边的大于后边的则交换
            if (arr[i].CompareTo(arr[j])>0)
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    //转为字符串数组
    string[] strArr = arr.Select(s => s.ToString()).ToArray();

    //拼接字符串
    string str = string.Join(",", strArr);

    //打印字符串
    Debug.Log(str);
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//快速排序单元
private int sortUnit(int[] arr, int left, int right)
{
    //此处选择第一个数作为基准值
    int pivot = arr[left];

    while (left<right)
    {
        //从后向前搜索比基准值小的元素
        while (right > left && arr[right] > pivot)
        {
            //右边下标左移
            --right;
        }

        //比基准值小的(等于的)元素放在左边
        arr[left] = arr[right];

        //从前向后搜索比基准值大（等于）的元素
        while (right > left && arr[left] <= pivot)
        {
            //左边下标右移
            ++left;
        }

        //比基准值大的的元素放在左边
        arr[right] = arr[left];
    }

    //左边的元素小于或等于基准值，右边的则大于基准值，此时左右下标相等，将基准值放在下标当前位置
    arr[left] = pivot;

    //返回此时的下标
    return right;
}

//递归调用
private void QuickMain(int[] arr,int left,int right)
{

    //如果起点下标和终点下标一样直接返回空
    if (left >= right)
    {

        return;
    }

    //完成一次单元排序
    int index = sortUnit(arr, left, right);

    //对左边单元进行排序
    QuickMain(arr, left, index - 1);
    //对右边边单元进行排序
    QuickMain(arr, index+1, right);
}

/*
* 快速排序:
* 1.在数组里面找出一个基准值，通常选取第一个数作为基准值
* 2.依据基准值，对数组进行分区操作，使左边的元素小于或等于基准值，右边的元素大于基准值
*
*/
private void QuickSort()
{
    //定义数组
    int[] arr = { 80, 10, 5, 40, 60, 1, 20, 10 };

    //开始快速排序
    QuickMain(arr, 0, arr.Length - 1);


    //转为字符串数组
    string[] strArr = arr.Select(s => s.ToString()).ToArray();

    //拼接字符串
    string str = string.Join(",", strArr);

    //打印字符串
    Debug.Log(str);
}