常见排序算法及其实现

冒泡排序

比较简单无脑的排序算法，在数据量很小的时候可以用一用。

稳定性：稳定
时间复杂度：O(n^2)
空间复杂度：O(1)

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


void BubbleSort<T>(IList<T> collection, bool descending = false) where T : IComparable<T>
{
    var mul = descending ? -1 : 1;
    
    for (var i = 0; i < collection.Count - 1; i++)
    {
        var sorted = true;
        for (var j = 0; j < collection.Count - i - 1; j++)
        {
            if (collection[j].CompareTo(collection[j + 1]) * mul > 0)
            {
                // Using syntactic sugar to swap
                (collection[j], collection[j + 1]) = (collection[j + 1], collection[j]);
                sorted = false;
            }
        }

        // If the list is sorted, we should stop comparing
        if (sorted)
        {
            break;
        }
    }
}

选择排序

同冒泡排序相比，没有本质区别。

稳定性：不稳定
时间复杂度：O(n^2)
空间复杂度：O(1)

C# 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void SelectionSort<T>(IList<T> collection, bool descending = false) where T : IComparable<T>
{
    var mul = descending ? -1 : 1;
    
    for (var i = 0; i < collection.Count - 1; i++)
    {
        var lastIndex = collection.Count - 1 - i;
        for (var j = 0; j < lastIndex; j++)
        {
            if (collection[j].CompareTo(collection[lastIndex]) * mul  > 0)
            {
                (collection[j], collection[lastIndex]) = (collection[lastIndex], collection[j]);
            }
        }
    }
}

插入排序

对于每一个未排序数据，将其插入到有序序列的合适位置。

稳定性：稳定
时间复杂度： O(n^2)
空间复杂度： O(1)

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


void InsertionSort<T>(IList<T> collection, bool descending = false) where T : IComparable<T>
{
    var mul = descending ? -1 : 1;

    for (var i = 1; i < collection.Count; i++)
    {
        var tmp = collection[i];
        for (var j = i - 1; j >= 0; j--)
        {
            if (collection[j].CompareTo(tmp) * mul > 0)
            {
                collection[j + 1] = collection[j];
                if (j == 0)
                {
                    collection[0] = tmp;
                }
            }
            else
            {
                collection[j + 1] = tmp;
                break;
            }
        }

        PrintCollection(collection);
        
    }
}