面試過(guò)程中常見的排序算法問題你見個(gè)？附常見排序算法源代碼
在面試過(guò)程中，排序算法常常是一個(gè)重要的考點(diǎn)。排序算法的熟練掌握不僅能展現(xiàn)出候選人對(duì)基本數(shù)據(jù)結(jié)構(gòu)的理解，也能展示出他們的算法設(shè)計(jì)和問題解決能力。下面我們將詳細(xì)討論幾種常見的排序算法及其在面試中的應(yīng)用。
一、選擇排序（Selection Sort）
選擇排序是一種簡(jiǎn)單直觀的排序算法，它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
Java源代碼示例：
public static void selectionSort(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;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}二、冒泡排序（Bubble Sort）
冒泡排序的工作原理是，對(duì)相鄰的元素進(jìn)行兩兩比較，順序相反則進(jìn)行交換，這樣每一輪過(guò)后最?。ɑ蜃畲螅┑脑貢?huì)被移到序列的最后。
Java源代碼示例：
public static void bubbleSort(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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}三、插入排序（Insertion Sort）
插入排序的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
Java源代碼示例：
public static void insertionSort(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;
}
}四、快速排序（Quick Sort）
快速排序是一種分治的排序算法，它將原始數(shù)據(jù)分割成兩個(gè)或更多的子序列，然后對(duì)每個(gè)子序列進(jìn)行排序，最后將有序的子序列合并為整體有序序列。
Java源代碼示例：
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 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 temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}五、歸并排序(Merge Sort)
歸并排序也是一種分治的排序算法，它將原始數(shù)據(jù)分割成兩個(gè)或更多的子序列，然后對(duì)每個(gè)子序列進(jìn)行排序，最后將有序的子序列合并為整體有序序列。但是，歸并排序采用了分治與合并相互獨(dú)立的方式進(jìn)行設(shè)計(jì)。在每一步的處理上，歸并排序?qū)⑿蛄蟹譃閮刹糠诌M(jìn)行獨(dú)立的排序，然后合并成一個(gè)有序的序列。這種設(shè)計(jì)方式使得歸并排序在處理大數(shù)據(jù)量的情況下表現(xiàn)得更好。
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
sortProcess(arr, 0, arr.length - 1);
}
public static int[] getSubArray(int[] arr, int l, int r) {
int[] subArr = new int[r - l + 1];
for (int i = 0; i < subArr.length; i++) {
subArr[i] = arr[l + i];
}
return subArr;
}
public static void sortProcess(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
sortProcess(arr, l, m);
sortProcess(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int[] leftArr = getSubArray(arr, l, m);
int[] rightArr = getSubArray(arr, m + 1, r);
int left = 0;
int right = 0;
int index = l;
while (left < leftArr.length && right < rightArr.length) {
if (leftArr[left] <= rightArr[right]) {
arr[index] = leftArr[left];
left++;
} else {
arr[index] = rightArr[right];
right++;
}
index++;
}
while (left < leftArr.length) {
arr[index] = leftArr[left];
left++;
index++;
}
while (right < rightArr.length) {
arr[index] = rightArr[right];
right++;
index++;
}
}
}使用方法：
public static void main(String[] args) {
int[] arr = {5, 3, 2, 6, 8, 1};
MergeSort mergeSort = new MergeSort();
mergeSort.mergeSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}這個(gè)程序會(huì)對(duì)數(shù)組進(jìn)行歸并排序，排序后的數(shù)組會(huì)打印出來(lái)。注意，這是一個(gè)基本的歸并排序?qū)崿F(xiàn)，它可能不適用于所有可能的輸入。如果你有特定的排序需求或大型數(shù)據(jù)集，可能需要優(yōu)化該算法或使用其他算法。
