数据结构与算法面试题

系统管理员 2021-09-20 10:40 357阅读 0赞

1，冒泡排序

class Program
        {
            static void Main(string[] args)
            {
                int[] array = { 4, 6, 34, 75, 43, 7, 356, 2 };
                BubbleSort(array );
     
                for (int i = 0; i < array .Length; i++)
                {
                    Console.Write(array [i] + " ");
                }
     
                Console.ReadKey();
            }
            public static void BubbleSort(int[] array)//冒泡排序
            {
                for (int i = 1; i < array.Length; i++)
                {
                    for (int j = 0; j < array.Length - i; j++)
                    {
                        //现在是升序。若想为降序，只需改为array [j ]<array[j + 1]即可。
                        if (array[j] > array[j + 1])
                        {
                            int tmp = array[j + 1];
                            array[j + 1] = array[j];
                            array[j] = tmp;
                        }
                    }
                }
            }
        }

2，快速排序

class Program
        {
            static void Main(string[] args)
            {
                int[] array = new int[] { 1, 24, 6, 7, 3, 78 };
                Console.Write("快速排序：");
                Sort.QuickSort(array, 0, array.Length - 1);
     
                for (int i = 0; i < array.Length; i++)
                {
                    Console.Write(array[i].ToString() + "  ");
                }
     
                Console.ReadKey();
            }
        }
        public class Sort
        {
            /// <summary>
            /// 快速排序
            /// </summary>
            /// <param name="arr">待排序的数组</param>
            /// <param name="low">第一个记录的索引</param>
            /// <param name="high">最后一个记录的索引</param>
            public static void QuickSort(int[] arr, int low, int high)
            {
                if (low > high)
                {
                    return;
                }
                int pivot = arr[low];
                int i = low + 1;
                int j = high;
                while (i < j)
                {
                    while ((i < j) && pivot >= arr[i])//注意：i<j可以不带等号，但pivot >= arr[i]要带等号
                    {
                        i++;
                    }
                    while ((i <= j) && pivot <= arr[j]) //注意：这两个都要带等号！！
                    {
                        j--;
                    }
                    if (i < j)
                    {
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                if (low < j)
                {
                    int temp = arr[low];
                    arr[low] = arr[j];
                    arr[j] = temp;
                }
                QuickSort(arr, low, j - 1);
                QuickSort(arr, j + 1, high);
            }
        }