【算法与数据结构】--高级算法和数据结构--排序和搜索

一、常见排序算法

以下是一些常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法的讲解以及附带C#和Java示例：

1.1 冒泡排序 (Bubble Sort)

讲解： 冒泡排序是一种简单的比较排序算法。它多次遍历待排序的元素列表，比较每一对相邻元素，如果它们的顺序不正确，就交换它们，直到没有需要交换的元素。
C# 示例：

using System;public class BubbleSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例：

public class BubbleSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.2 选择排序 (Selection Sort)

讲解： 选择排序是一种简单的排序算法。它将待排序列表分为已排序和未排序两部分，然后从未排序部分选择最小的元素，与已排序部分的最后一个元素交换位置，直到整个列表排序完成。
C# 示例：

using System;public class SelectionSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[minIndex]){minIndex = j;}}// 交换 arr[i] 和 arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例：

public class SelectionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换 arr[i] 和 arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.3 插入排序 (Insertion Sort)

讲解： 插入排序是一种简单的排序算法。它将待排序列表分为已排序和未排序两部分，然后逐个将未排序部分的元素插入到已排序部分的合适位置，直到整个列表排序完成。
C# 示例：

using System;public class InsertionSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 1; i < n; i++){int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例：

public class InsertionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.4 快速排序 (Quick Sort)

讲解： 快速排序是一种高效的分治排序算法。它选择一个基准元素，将列表分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。
C# 示例：

using System;public class QuickSort
{public static void Sort(int[] arr, int low, int high){if (low < high){int pivot = Partition(arr, low, high);Sort(arr, low, pivot - 1);Sort(arr, pivot + 1, high);}}public static int Partition(int[] arr, int low, int high){int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++){if (arr[j] < pivot){i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp2 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp2;return i + 1;}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int n = arr.Length;Sort(arr, 0, n - 1);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例：

public class QuickSort {public static void sort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);sort(arr, low, pivot - 1);sort(arr, pivot + 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp2 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp2;return i + 1;}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int n = arr.length;sort(arr, 0, n - 1);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.5 归并排序 (Merge Sort)

讲解： 归并排序是一种高效的分治排序算法。它将列表递归地分为较小的子列表，然后合并这些子列表以获得排序的结果。
C# 示例：

using System;public class MergeSort
{public static void Sort(int[] arr){int n = arr.Length;if (n > 1){int mid = n / 2;int[] left = new int[mid];int[] right = new int[n - mid];for (int i = 0; i < mid; i++){left[i] = arr[i];}for (int i = mid; i < n; i++){right[i - mid] = arr[i];}Sort(left);Sort(right);int i = 0, j = 0, k = 0;while (i < left.Length && j < right.Length){if (left[i] < right[j]){arr[k] = left[i];i++;}else{arr[k] = right[j];j++;}k++;}while (i < left.Length){arr[k] = left[i];i++;k++;}while (j < right.Length){arr[k] = right[j];j++;k++;}}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例：

public class MergeSort {public static void sort(int[] arr) {int n = arr.length;if (n > 1) {int mid = n / 2;int[] left = new int[mid];int[] right = new int[n - mid];for (int i = 0; i < mid; i++) {left[i] = arr[i];}for (int i = mid; i < n; i++) {right[i - mid] = arr[i];}sort(left);sort(right);int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] < right[j]) {arr[k] = left[i];i++;} else {arr[k] = right[j];j++;}k++;}while (i < left.length) {arr[k] = left[i];i++;k++;}while (j < right.length) {arr[k] = right[j];j++;k++;}}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

这些是常见的排序算法，每种排序算法都有其独特的方式来对数据进行排序。无论使用C#还是Java，你可以根据需要选择合适的算法来排序你的数据。

二、搜索算法

以下是一些常见的搜索算法，包括线性搜索、二分搜索和哈希表查找。每种搜索算法的讲解以及附带C#和Java示例：

2.1 线性搜索 (Linear Search)

讲解： 线性搜索是一种简单的搜索算法，它从列表的开头开始逐个检查元素，直到找到目标元素或搜索整个列表。
C# 示例：

using System;public class LinearSearch
{public static int Search(int[] arr, int target){for (int i = 0; i < arr.Length; i++){if (arr[i] == target){return i; // 返回目标元素的索引}}return -1; // 未找到目标元素}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int target = 22;int result = Search(arr, target);if (result != -1){Console.WriteLine("Element found at index: " + result);}else{Console.WriteLine("Element not found in the array.");}}
}

Java 示例：

public class LinearSearch {public static int search(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i; // 返回目标元素的索引}}return -1; // 未找到目标元素}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int target = 22;int result = search(arr, target);if (result != -1) {System.out.println("Element found at index: " + result);} else {System.out.println("Element not found in the array.");}}
}

2.2 二分搜索 (Binary Search)

讲解： 二分搜索是一种高效的搜索算法，前提是待搜索的列表必须是已排序的。它通过将目标值与中间元素进行比较，然后排除一半的列表，继续在剩余的一半中搜索，以此类推，直到找到目标元素或确定它不存在。
C# 示例：

using System;public class BinarySearch
{public static int Search(int[] arr, int target){int left = 0;int right = arr.Length - 1;while (left <= right){int mid = left + (right - left) / 2;if (arr[mid] == target){return mid; // 返回目标元素的索引}if (arr[mid] < target){left = mid + 1;}else{right = mid - 1;}}return -1; // 未找到目标元素}public static void Main(){int[] arr = { 11, 12, 22, 25, 34, 64, 90 };int target = 22;int result = Search(arr, target);if (result != -1){Console.WriteLine("Element found at index: " + result);}else{Console.WriteLine("Element not found in the array.");}}
}

Java 示例：

public class BinarySearch {public static int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 返回目标元素的索引}if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 未找到目标元素}public static void main(String[] args) {int[] arr = { 11, 12, 22, 25, 34, 64, 90 };int target = 22;int result = search(arr, target);if (result != -1) {System.out.println("Element found at index: " + result);} else {System.out.println("Element not found in the array.");}}
}

2.3 哈希表查找 (Hash Table Lookup)

讲解： 哈希表查找是一种使用哈希函数将键映射到值的数据结构。它允许快速查找键对应的值，通常具有恒定的查找时间。
C# 示例：

using System;
using System.Collections.Generic;public class HashTableLookup
{public static void Main(){Dictionary<string, int> phonebook = new Dictionary<string, int>();// 添加元素到哈希表phonebook["Alice"] = 123456789;phonebook["Bob"] = 987654321;phonebook["Charlie"] = 555555555;// 查找元素if (phonebook.ContainsKey("Bob")){int phoneNumber = phonebook["Bob"];Console.WriteLine("Bob's phone number is: " + phoneNumber);}else{Console.WriteLine("Bob's phone number not found.");}}
}

Java 示例：

import java.util.HashMap;
import java.util.Map;public class HashMapLookup {public static void main(String[] args) {Map<String, Integer> phonebook = new HashMap<>();// 添加元素到哈希表phonebook.put("Alice", 123456789);phonebook.put("Bob", 987654321);phonebook.put("Charlie", 555555555);// 查找元素if (phonebook.containsKey("Bob")) {int phoneNumber = phonebook.get("Bob");System.out.println("Bob's phone number is: " + phoneNumber);} else {System.out.println("Bob's phone number not found.");}}
}

这些是常见的搜索算法，每种算法都适用于不同的情况。线性搜索适用于未排序的列表，二分搜索适用于已排序的列表，而哈希表查找适用于键值对的存储和检索。你可以根据你的需求选择适当的搜索算法。

三、总结

本文介绍了常见的排序算法和搜索算法。排序算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序，它们分别用于按不同方式对数据进行排序。每个算法都伴随着C#和Java的示例代码。搜索算法包括线性搜索、二分搜索和哈希表查找，用于在数据集中查找特定元素。这些算法有各自的优点和适用场景，可以根据需求选择合适的算法。