八大内部排序以及稳定性

xiaoxiao2025-10-10 5

稳定性的定义：如果队列中存在相等的两个数字，如果数字在排序过程中不发生变化，则是稳定的排序，如果发生了变化则是不稳定的排序。

回忆的过程：以后看过，长时间没写了，从头写一遍，跟以前写的比较比较看看自己有什么改进。

初级菜鸟，如果问题望指出，多多沟通，有利于成长。

1. 交换排序：冒泡排序、快排排序。

(1) 冒泡思路：每次循环大的往下沉，每次循环循环的长度-1。swap方法为自定义方法交换在博客最后面

/* * 冒泡排序交换排序顾名思义，假如某个位置的数据是确定的，寻找相应条件的数据进行交换，例如：数组{ 49, 38, 65, 97, 76, 13, * 27, 49 }。我采用从小到大的排序方式假如49就是已经确定位置的数据，从数据38开始遍历，38小于49，交换位置。以此类推。 * */ public static int[] bubbleSort(int arr[]) { int le = arr.length - 1; while (le >= 0) { int inter = arr[0]; int index = 0; for (int j = 1; j <= le; j++) { if (arr[j] < inter) /* * 对于稳定性的概念也不是绝对的，如果此处的条件是arr[j] <= inter * 那么这个冒泡排序就是不稳定的排序，所有有的时候稳定是相对的跟自己定义的条件有关系的 */ swap(arr, index, j); else inter = arr[j]; index = j; } le--; } return arr; } (2) 快排思路：设置一个标志位，从前面找比标志位小的从后面找比标志位大的，分治递归。

public static void quickSort(int arr[], int from, int to) { if (from >= to) return; // 标志位，将比标志位小的放到某个数的前面，将比标志位大的放到标志位的后面，递归解决--分治法 int temp = arr[from]; // 每次交换的位置 int index = from; int start = from; int end = to; while (start < end) { // 从后往前找比标志位元素小的， while (start < end && arr[end] >= temp) end--; if (arr[end] < temp) { arr[index] = arr[end]; index = end; } while (start < end && arr[start] < temp) start++; if (arr[start] > temp) { arr[index] = arr[start]; index = start; } } // 在最后一个交换的位置添加标志位，标志位可以将问题分解为两个不同的问题 arr[index] = temp; quickSort(arr, from, index - 1); quickSort(arr, index + 1, to); }

2. 插入排序：插入排序、希尔排序。

(1) 插入排序：设置一个标志位，假设第一元素是排好序的，与第下一个元素进行比较，大与直接进行下一个，小于需要找到该元素插入的恰当的位置。

public static void insertSort(int arr[]) { int le = arr.length - 1; // 元素比较的位置 int start = 1; int temp = arr[0]; while (start <= le) { if (arr[start] < temp) { int index = start - 1; int inNum = arr[start]; /* * 移动元素： 38，49,,65, 76, 97，13, 27, 49 * 例如如果start在13位置，需要找到13的恰当的位置，与前一个元素（97）进行比较，如果前一个元素（97）>13, * 则将这个元素往后移动,找到13位置的过程也就是不断的将元素往后推一个位置，如果小于则直接进行下一轮的循环,即start++ * ; */ while (index >= 0 && inNum <= arr[index]) { arr[index + 1] = arr[index]; index--; } if (index == -1) arr[0] = inNum; else arr[index + 1] = inNum; } else temp = arr[start]; start++; } }

(2) 希尔排序：主要就是取步长，比较步长之间数字的大小

public static void shellSort(int arr[]) { /* * 希尔本质上和插入排序是一样的，但是它比较的不是相邻元素的大小而是比较步长之间的元素的大小，说不太清楚，举个例子：数组49, 38, * 65, 97, 76, 13, 27, 49 。如果步长为3，则39,97,27一组之间比较， * 38,76,49之间比较，等等。我自己理解哈：这样做的好处可以把相对小的数前移，相对大的数后移，这样就避免了插入排序中插入13的时候， * 移动那么多数。 */ int step = arr.length / 2; int le = arr.length - 1; int m = 0; // 元素比较的位置 while (step > 0) { int temp = arr[0]; int start = step; while (start <= le) { temp = arr[start - step]; if (arr[start] < temp) { int index = start - step; int inNum = arr[start]; /* * 移动元素： 38，49,,65, 76, 97，13, 27, 49 * 例如如果start在13位置，需要找到13的恰当的位置，与前一个元素（97）进行比较，如果前一个元素（97）> * 13, 则将这个元素往后移动,找到13位置的过程也就是不断的将元素往后推一个位置，如果小于则直接进行下一轮的循环, * 即start++ ; */ while (index >= 0 && inNum <= arr[index]) { arr[index + step] = arr[index]; index -= step; } arr[index + step] = inNum; } start++; } step--; } }

3.选择排序

(1) 选择排序:每次循环选择数组中最小的或者最大的。

public static void selectSort(int arr[]) { for (int i = 0; i < arr.length; i++) { //每次循环之前I之前的元素是已经被排序好的，i之后是未排序的，假设当前元素I是最小的，在I之后去寻找比I小的。 int min = arr[i]; int index = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < min) { min = arr[j]; index = j; } } swap(arr, i, index); } }

(2) 堆排序:构建大顶堆或者小顶堆，交换第一元素和最后元素，继续构建堆的过程。

/* * 从i = arr.length / 2 * -1(-1是因为数组的下标从0开始的)一半元素开始进行操作的，所以首先要知道当前节点有一个节点还是有两个节点这个方法是完成构建小顶堆 */ public static int[] heapSort(int arr[], int i, int le) { while (i >= 0 && 2 * i + 1 <= le) { // 右节点 int r = 2 * i + 2; // 左节点 int l = 2 * i + 1; int min = 0; int minIndex = 0; /* * 判断当前节点是有一个孩子节点还是两个孩子节点，第一次(step=3)判断的时候 * 当r=le时说明有两个孩子节点，否则有个一个孩子节点，其他的次数(step=2,1,0)均有两个节点 */ if (r <= le) { // 取孩子节点中最小的节点 if (arr[r] > arr[l]) { min = arr[l]; minIndex = l; } else { min = arr[r]; minIndex = r; } // 判断最小的节点和父节点大小, if (min < arr[i]) { swap(arr, i, minIndex); /* * 在交换之后，元素的位置发生变化了，在i位置的元素不需要做什么，因为下一个进行操作的是i-1，依次往下进行， * 它会自动的检测到他的父节点是不是小于它的两个子节点，但是它的子节点并不知道交换之后满足不满足这个要求， * 所以需要检查一下-ps：这个你按照数组把堆画出来，然后自己交换13和49的时候你就会发现了，父节点49子节点65, * 27 */ heapSort(arr, minIndex, le); } } else { /* * 当前节点只有一个孩子节点时，只有在第一次执行的时候可能发生，所以直接比较即可 */ if (arr[i] > arr[l]) swap(arr, i, l); } i--; } // heapSortRemove(arr, 0, le); return arr; } /* * 小顶堆排序，每次将最小的交换到最后一个节点，切长度-1,然后在进行构建小顶堆 */ public static int[] heapSortRemove(int arr[], int le) { while (le >= 0) { int temp = arr[0]; arr[0] = arr[le]; arr[le] = temp; le--; /* * 调用heapSort方法时，因为它只换了最后一个元素和第一个元素，所以检查第一元素即可 */ heapSort(arr, 0, le); } return arr; }

注意：大顶堆在每一次交换的时候将最大的交换到最后一个位置，所以大顶堆的结果数组是从小到大排列的。小顶堆则是恰恰相反，从大到小。

4.归并排序

思路：主要应用分治法，将问题分解成小的问题，进行排序，然后合并进行排序。

/* * 将数组分成两部分，(0,3)、(4,7)-再分成两部分(0,1)(2-3)等，直到(0,0)停止 ,之后合并(0,1),(0,3),(0,7)。 */ public static void mergeSort(int arr[], int from, int to, int temp[]) { if (from < to) { int mid = (from + to) / 2; mergeSort(arr, from, mid, temp); mergeSort(arr, mid + 1, to, temp); mergearray(arr, from, mid, to, temp); } } /* * 如果是两个元素（0，1），将两个元素两个元素排序,，如果是4个（0，4）元素将四个元素排序，temp作为中间数组,将排序的值，暂时保存下来, * 之后保存到arr中。 */ public static void mergearray(int arr[], int from, int mid, int to, int temp[]) { int i = from; int inter = mid + 1; int k = 0; while (from <= mid && inter <= to) { if (arr[from] < arr[inter]) temp[k++] = arr[from++]; else temp[k++] = arr[inter++]; } while (from <= mid) temp[k++] = arr[from++]; while (inter <= to) temp[k++] = arr[inter++]; for (int j = 0; j < k; j++) { arr[j + i] = temp[j]; } }

5.交换方法swap

public static void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

6.主函数

public static void main(String[] args) { int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49, 24 }; // 冒泡排序 // int a[] = bubbleSort(arr); // 快排排序 // quickSort(arr, 0, a,rr.length - 1); // 插入排序 // insertSort(arr); // 希尔排序 // shellSort(arr); // 选择排序 // selectSort(arr); // 堆排序 // arr = heapSort(arr, arr.length / 2 - 1, arr.length - 1); // arr = heapSortRemove(arr, arr.length - 1); // 归并排序 int temp[] = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }

6. 各个排序算法的稳定性

转载位置：http://www.cnblogs.com/pangxiaodong/archive/2011/08/19/2145260.html

基数排序我并没有写，这个我没研究，有空会有后续的。

转载请注明原文地址: https://ju.6miu.com/read-1303020.html

最新回复(0)