VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > C#教程 >
  • 算法-2 选择排序、冒泡排序、插入排序

一 选择排序

选择排序的时间复杂度O(n2),额外空间复杂度O(1)

复制代码
public static void SelectionSort(int[] arr)
{
    if (arr == null || arr.Length < 2)
    {
        return;
    }

    for (int i = 0; i < arr.Length - 1; i++)// i ~ n-1
    {
        int minIndex = i;   
        for (int j = i + 1; j < arr.Length; j++)// i+1 ~ n 上找到最小值的下标
        {
            //从 i+1 的位置开始,逐个比较,得出最小值的索引
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        //交换 i 位置 和 最小值索引位置的值
        Swap(arr, i, minIndex);
    }
}

public static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
复制代码

 

二 冒泡排序

冒泡排序的时间复杂度O(n2),额外空间复杂度O(1)

复制代码
public static void BubbleSort(int[] arr)
{
    if (arr == null || arr.Length < 2)
    {
        return;
    }

    for (int e = arr.Length - 1; e > 0; e--)// e 从数组长度开始,逐渐缩小 e 范围
    {
        for (int i = 0; i < e; i++)         // i 从 0 开始遍历 到 e 
        {
            if (arr[i] > arr[i + 1])        // 如果 i 位置的值 大于 i+1 位置的值,交换
            {
                Swap(arr, i, i + 1);
            }
        }
    }
}

public static void Swap(int[] arr,int i,int j) 
{
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}
复制代码

 

三 插入排序

 插入排序的时间复杂度O(n2),额外空间复杂度O(1)。最好情况下时间复杂度O(n)

复制代码
public static void InsertionSort(int[] arr)
{
    if (arr == null || arr.Length < 2)
    {
        return;
    }
    for (int i = 1; i < arr.Length; i++) //在 0 ~ i 范围内做到有序
    {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
        {
            Swap(arr, j, j + 1);
        }
    }
}
public static void Swap(int[] arr, int i, int j)
{
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}
复制代码

 

四 异或运算 ^

4.1 关于异或运算

如果 x 计算结果为 true 且 y 计算结果为 false,或者 x 计算结果为 false 且 y 计算结果为 true,那么 x ^ y 的结果为 true。否则,结果为 false。
也就是说,对于 bool 操作数,^ 运算符的计算结果与不等运算符!= 相同。即相异为true,相同为false。

Console.WriteLine(true ^ true);    // output: False
Console.WriteLine(true ^ false);   // output: True
Console.WriteLine(false ^ true);   // output: True
Console.WriteLine(false ^ false);  // output: False

而对于整型数值类型的操作数,^ 运算计算其操作数的位逻辑异或。

uint a = 0b_1111_1000;
uint b = 0b_0001_1100;
uint c = a ^ b;
Console.WriteLine(Convert.ToString(c, toBase: 2));
// Output:
// 11100100

对于整型操作数的异或,可以理解为无进位相加。

4.2 异或运算的性质

异或运算满足交换律和结合律。

a ^ b ^ c == a ^ c ^ b == b ^ ( a ^ c )

0 ^ n == 0 , n ^ n == 0

4.3 异或运算的应用

4.3.1 已知一个整型数组中只有一个数出现了奇数次,其他数出现了偶数次。如何找到这个数?要求时间复杂度O(n),额外空间复杂度O(1)。

复制代码
public static void PrintOddTimesNum1(int[] arr)
{
    int eor = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        eor = eor ^ arr[i];
    }
    Console.WriteLine(eor);
}
复制代码

4.3.2 已知一个整型数组中只有两个数出现了奇数次,其他数出现了偶数次。如何找到这两个数?要求时间复杂度O(n),额外空间复杂度O(1)。

复制代码
public static void PrintOddTimesNum2(int[] arr)
{
    int eor = 0;

    foreach (var item in arr)
    {
        eor = eor ^ item;
    }
    // eor = a ^ b
    // 因为 a!= b,所以 eor!= 0,则 eor必然有一位是1
    int rightOne = eor & (~eor + 1); //取出eor最右边的1
    int onlyOne = 0;
    foreach (var item in arr)
    {
        if ((item & rightOne) == 0)
        {
            onlyOne = onlyOne ^ item;
        }
    }
    Console.WriteLine(onlyOne);
    Console.WriteLine(onlyOne ^ eor);
}
复制代码

 

五 局部最小值问题

给定一个长度为n的无序数组,任何两个相邻的数不相等,如果0位置比1位置小,则0位置是局部最小,如果n-2位置比n-1位置小,则n-1位置是局部最小,

如果中间位置 i 比 i - 1 位置小且比 i + 1 位置小,则 i 位置是局部最小。

求一个局部最小值的位置,要求时间复杂度O(log n)

复制代码
public static int GetLocalMinimum(int[] arr)
{
    if (arr == null || arr.Length == 0)
    {
        return -1;
    }
    if (arr.Length == 1 || arr[0] < arr[1])
    {
        return 0;
    }
    if (arr[arr.Length - 1] < arr[arr.Length - 2])
    {
        return arr.Length - 1;
    }

    int mid = 0;
    int left = 1;
    int right = arr.Length - 2;
    while (left < right)
    {
        mid = left + ((right - left) >> 1);
        if (arr[mid - 1] < arr[mid])
        {
            right = mid - 1;
        }
        else if (arr[mid + 1] < arr[mid])
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return left;
}
复制代码

 

以上。

出处:https://www.cnblogs.com/wwwen/p/16905540.html


相关教程