赞
踩
冒泡排序(Bubble Sorting)的基本思想:
通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。
public void BubbleSort(){ int arr[] = {3, 9, -1, 10, 20}; int temp = 0; // 临时变量 boolean flag = false; // 标识变量,表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) {//固定i个 // 如果前面的数比后面的数大,则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (!flag) { // 在一趟排序中,一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 } } System.out.println(Arrays.toString(arr)); }
基本介绍
选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。
选择排序思想:
选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[0]~arr[n-1]
中选取最小值,与arr[0]交换,第二次从arr[1]~arr[n-1]
中选取最小值,与arr[1]交换,第三次从arr[2]~arr[n-1]
中选取最小值,与arr[2]交换,…,第i次从arr[i-1]~arr[n-1]
中选取最小值,与arr[i-1]交换,…, 第n-1次从arr[n-2]~arr[n-1]
中选取最小值,与arr[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。
public void SelectSort(){ int arr[] = {3, 9, -1, 10, 20}; for (int i = 0; i < arr.length-1; i++) {//可以减一 int minVal = arr[i]; int minIndex=i; for (int j = i+1; j < arr.length; j++) { if(minVal>arr[j]){ minVal=arr[j]; minIndex=j; } } if(minIndex != i) { arr[minIndex] = arr[i]; arr[i] = minVal; //定义了minVal变量,就不用定义temp交换了。妙! } } System.out.println(Arrays.toString(arr)); }
插入排序法介绍:
插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。
插入排序法思想:
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
public void Insert(){ int arr[] = {3, 9, -1, 10, 20}; int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { insertVal=arr[i]; //待插入值 insertIndex= i - 1; //指向arr[i]的前面这个数的下标 while(insertIndex >= 0 && insertVal<arr[insertIndex]){//注意:是大于等于零 arr[insertIndex+1] = arr[insertIndex]; //未到达指定位置时,(前方)比它大的值向后移,而新添加的最后一个数已给insertVal。妙! insertIndex--; } arr[insertIndex + 1] = insertVal; } System.out.println(Arrays.toString(arr)); }
希尔排序法介绍
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。
希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
public void Shell(){
int arr[] = {3, 9, -1, 10, 20};
int temp = 0;
for(int gap = arr.length/2;gap>0;gap /= 2)//共gap组
for (int i = gap; i < arr.length; i++)
for (int j = i- gap; j >= 0; j -= gap)//第i个下标的值以gap为步长,与前方(同组)一一比较
if (arr[j] > arr[j + gap]) {// 若大于 加上 步长的倍数的那个元素,说明交换
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
System.out.println(Arrays.toString(arr));
}
对交换式的希尔排序进行优化->移位法,妙!!!!
public void ShellInsert(){
int arr[] = {3, 9, -1, 10, 20};
for(int gap = arr.length/2;gap>0;gap /= 2)//共gap组
for (int i = gap; i < arr.length; i++){
int temp = arr[i];
int index = i - gap;//指向前第gap个,与插入排序异曲同工之妙!!
while(index>=0 && temp<arr[index]){
arr[index + gap] =arr[index];
index -= gap;
}
arr[index + gap] = temp;
}
System.out.println(Arrays.toString(arr));
}
快速排序法介绍:
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
public void Quick() { int arr[] = {2,10,8,22,34,5,12,28,21,11,10}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr,int left,int right){ int l=left; int r=right; int pivot = arr[(left + right) / 2];//pivot 中轴值 int temp=0; while(l<r){//比pivot 值小放到左边,比pivot 值大放到右边 while(arr[l]<pivot){ l++; } while(arr[r]>pivot){ r--; } if(l>=r){ break; } temp=arr[l]; arr[l]=arr[r]; arr[r]=temp; if(arr[l] == pivot)r--;//防止有相等,进入死循环, if(arr[r] == pivot)l++;//若交换后的右边的值 与 中轴值的相等,左边一定是比pivot小的值 } if(l == r){// 如果 l == r,(中间就是pivot), 必须l++, r--, 否则为出现栈溢出!!!! l++; r--; } if(left<r)//当只有一个值时,此处l++,r--,就不会再进入递归 quickSort(arr,left,r); if(right>l) quickSort(arr,l,right); }
归并排序介绍:
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
说明:
可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程。
合并相邻有序子序列:
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤
public void MergeSort() { int arr[] = {8, 4, 5, 7, 1, 3, 6, 2}; int temp[] = new int[arr.length]; mergeSort(arr, 0, arr.length-1, temp); System.out.println("归并排序后=" + Arrays.toString(arr)); } public static void mergeSort(int[] arr, int left, int right, int[] temp) {//分+合方法 if (left < right) {//分解到只有一个 int mid = (left + right) / 2; mergeSort(arr, left, mid, temp); //向左递归进行分解 mergeSort(arr, mid + 1, right, temp); //向右递归进行分解 merge(arr,left,mid,right,temp); } } public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 初始化 int j = mid + 1; int index = 0; // 指向temp数组的当前索引 while (i <= mid && j <= right) {//直到左右两边有一边处理完毕为止 if (arr[i] <= arr[j]) { temp[index] = arr[i]; index += 1; i += 1; }else{ temp[index] = arr[j]; index += 1; j += 1; } } //二,把有剩余数据的一边的数据依次全部填充到temp while(i<=mid){ temp[index] = arr[i]; index += 1; i += 1; } while (j<=right){ temp[index] = arr[j]; index += 1; j += 1; } //三,将temp数组的元素拷贝到arr,注意:并不是每次都拷贝所有 index = 0; int tempLeft = left; while(tempLeft <= right){ arr[tempLeft] = temp[index]; index += 1; tempLeft += 1; } }
基数排序(桶排序)介绍:
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展
基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。
基数排序的说明:
基数排序是对传统桶排序的扩展,速度很快.
基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序时,容易造成OutOfMemoryError 。
基数排序时稳定的。[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的]
有负数的数组,我们不用基数排序来进行排序, 如果要支持负数,参考: https://code.i-harness.com/zh-CN/q/e98fa9
基数排序基本思想
将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤
public void Radix() { int arr[] = {53, 3, 542, 748, 14, 214};//处理负数时需要改进 int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max < arr[i]) max = arr[i]; } int maxLength = (max + "").length();//得到最大数是几位数,妙!!! int[][] bucket = new int[10][arr.length]; int[] bucketElementCounts = new int[10];//比如:bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数 for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {//个十百...位 for (int j = 0; j < arr.length; j++) { int digitOfElement = arr[j] / n % 10;//个十百...位 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } int index = 0; for (int k = 0; k < bucketElementCounts.length; k++) {//遍历每一个桶 if (bucketElementCounts[k] != 0) { for (int l = 0; l < bucketElementCounts[k]; l++) {//遍历k桶的数 arr[index++] = bucket[k][l]; } } bucketElementCounts[k] = 0;//第i+1轮处理后,需要将每个 bucketElementCounts[k] = 0 !!!! } } System.out.println(Arrays.toString(arr)); }
堆排序基本介绍
堆排序的基本思想:
可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了.
public void Heap() { int arr[] = {4, 6, 8, 5, 9}; int temp = 0; //1.将无序序列构建成一个堆,根据升序(降序)需求选择大顶堆(小顶堆) for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } for (int j = arr.length - 1; j > 0; j--) { //2.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端; temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; //3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与j--元素,反复执行调整+交换步骤,直到整个序列有序。 adjustHeap(arr, 0, j); } System.out.println("数组=" + Arrays.toString(arr)); } public static void adjustHeap(int arr[], int i, int length) { int temp = arr[i]; for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//为最大元素沉底后交换做准备 if (k + 1 < length && arr[k] < arr[k + 1]) { k++;// k 指向右子结点 } if (arr[k] > temp) {//如果子结点大于父结点 arr[i] = arr[k]; i = k; } else { break; } arr[i] = temp; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。