IT面试笔试-各种排序算法Java实现

【IT面试笔试中的排序算法Java实现】 在IT面试和笔试中，掌握各种排序算法的实现是必不可少的技能。本文将详细介绍几种经典的排序算法，并提供Java语言的实现代码，包括冒泡排序、插入排序、选择排序和快速排序。这些算法不仅在面试中常被考察，而且在实际开发中也有广泛应用。 1. **冒泡排序（Bubble Sort）**： 冒泡排序是一种简单的交换排序方法，其时间复杂度为O(n*n)。它通过不断比较相邻元素并交换位置，使得较大的元素逐渐“冒”到数组的末尾。以下是Java实现的代码： ```java public class BubbleSort extends SortBase { public void bubbleSort(int[] array) { for (int i = 0; i < array.length; i++) for (int j = 0; j < array.length - i - 1; j++) if (array[j] > array[j + 1]) swap(array, j, j + 1); } } ``` 2. **插入排序（Insertion Sort）**： 插入排序分为直接插入和希尔排序两种。直接插入排序是将新元素与已排序部分进行比较，找到合适位置插入。时间复杂度也是O(n*n)。以下是两种实现方式的Java代码： ```java public class InsertSort extends SortBase { public void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { for (int j = 0; j < i; j++) { if (array[j] < array[i]) swap(array, i, j); } } } public void insertionSort(int[] a) { for (int p = 1; p < a.length; p++) { int tmp = a[p]; int j = p; for (; j > 0 && tmp < a[j - 1]; j--) a[j] = a[j - 1]; a[j] = tmp; } } } ``` 3. **选择排序（Selection Sort）**： 选择排序通过每轮找出未排序部分的最大（或最小）元素并放置到已排序部分的末尾，时间复杂度同样是O(n*n)。Java实现如下： ```java public class SelectSort extends SortBase { public void selectSort(int[] array) { for (int i = 0; i < array.length; i++) { int max_potion = i; for (int j = i + 1; j < array.length; j++) if (array[max_potion] < array[j]) max_potion = j; if (i != max_potion) swap(array, i, max_potion); } } } ``` 4. **快速排序（Quick Sort）**： 快速排序是一种效率较高的排序算法，平均时间复杂度为O(n log n)，最坏情况下为O(n*n)。快速排序的核心是“分治”策略，通过选取一个“轴点”将数组分为两部分，然后递归地对这两部分进行排序。以下是Java实现的代码片段： ```java public class QuickSort extends SortBase { public void quickSort(int[] array, int low, int high) { if (low < high) { int pivotIndex = partition(array, low, high); quickSort(array, low, pivotIndex - 1); quickSort(array, pivotIndex + 1, high); } } private int partition(int[] array, int low, int high) { int pivot = array[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; swap(array, i, j); } } swap(array, i + 1, high); return i + 1; } } ``` 以上代码展示了排序算法的Java实现，这些基础排序算法对于理解数据结构和算法原理至关重要。在面试或笔试中，能够熟练掌握并灵活运用这些算法，将有助于提升你的技术能力，并在竞争激烈的IT行业中脱颖而出。