插入排序是一种简单的排序算法，它的基本思想是：将数据分为已排序区和未排序区，在未排序区中取出一个元素，在已排序区中从后往前扫描，找到比该元素小的元素，将其插入到该元素的后面。
1、请简述插入排序的原理，并用Java代码实现：
插入排序是一种简单的排序算法，它的基本思想是：将数据分为已排序区和未排序区，在未排序区中取出一个元素，在已排序区中从后往前扫描，找到比该元素小的元素，将其插入到该元素的后面。
Java代码实现：
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
}
2、请简述快速排序的原理，并用Java代码实现：
快速排序是一种分治算法，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Java代码实现：
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int mid = partition(array, left, right);
quickSort(array, left, mid - 1);
quickSort(array, mid + 1, right);
}
}
private static int partition(int[] array, int left, int right) {
int pivot = array[left];
while (left < right) {
while (left < right && array[right] >= pivot) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= pivot) {
left++;
}
array[right] = array[left];
}
array[left] = pivot;
return left;
}
本站系公益性非盈利分享网址，本文来自用户投稿，不代表码文网立场，如若转载，请注明出处
评论列表（23条）