1. 快速排序(这里给出两种实现方法)
/**思路: * 1. 在数据集中,选择一个元素作为"基准(pivot)" * 2. 分区(partition):所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素都移到"基准"的右边 * 3. 分区操作结束后,基准元素所处的位置就是最终排序后它所处的位置 * 4. 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集都只剩下一个元素为止 * * @param arr 待排序数组 * @param low 数组第一个元素索引 * @param high 数组最后一个元素的索引 * @return 排序后的数组 */ public static int[] quickSort(int[] arr,int low,int high) { //对low和high进行大小判断(此处如果仅对数组arr做非空及是否有元素判断会出现栈溢出) if(low >= high) { return arr; } //将arr一分为二 int middleIndex = partition(arr,low,high); //对基准左边的进行递归排序 quickSort(arr,middleIndex-1); //对基准右边的进行递归排序 quickSort(arr,middleIndex+1,high); return arr; }
/**获得"基准"(默认是最低位low)在数组排序后所在位置 * @param arr 待查找数组 * @param low 开始位置 * @param high 结束位置 * @return "基准"所在位置 */ private static int partition(int[] arr,int high) { //每次都假设数组第一个位置的元素作为基准 int temp = arr[low]; while (low < high) { while (arr[high] >= temp && high > low) {//后半部分向前扫描 //将临时基准元素与其右边的元素依次比较,值大于等于它的将high-- //当low<=high时,获取到等于或小于临时基准元素的元素 high--; } //将小于或等于基准元素的元素移到基准元素左边最低端 arr[low] = arr[high]; while (arr[low] <= temp && high > low) {//从前半部分扫描 low++; } //将大于或等于基准元素的元素移到基准元素右边最高端 arr[high] = arr[low]; } //基准值 arr[low] = temp; //返回最终基准 return low; }
2. 选择排序(这里给出两种实现方法)
/** 思路: * 1. 首先从未排序的序列中找到最小的元素,放到排序序列的起始位置 * 2. 然后从剩余的未排序序列中继续查找最小元素,放置到已排序序列的末尾 * * 双层for循环: 遍历次数为数组长度-1,外层for循环遍历索引从0到arr.length-2; 内层for循环遍历索引从1到arr.length-1 */ public static int[] selectionSort(int[] arr) { //判断数组是否为空及是否有元素 if(arr==null || arr.length==0) { return arr; } //数组中有元素 //外层循环遍历数组目的是获取数组元素索引 for (int i = 0; i < arr.length - 1; i++) { //将每个索引都假设为最小值的索引 int min = i; for (int j = i + 1; j < arr.length; j++) { //此时min=i,将min位置的值跟其余的值比较 if(arr[j] < arr[min]) { //索引j处的值比假设最小值小 min = j; } } //元素位置交换获取升序排序(元素相同的0 0) int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } return arr; }
/**方法2: * 双层for循环: 遍历次数都是数组长度,遍历索引都是从0到arr.length-1 */ public static int[] selectSort(int[] arr) { //判断数组是否为空及是否有元素 if(arr==null || arr.length==0) { return arr; } int length = arr.length; for (int i = 0; i < length; i++) { int k = i;//待确定位置 //选择出应该在第i个位置的数 for (int j = length - 1; j > i; j--) { if(arr[j] < arr[k]) { k = j; } } //交换两个数 int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } return arr; }
3. 冒泡排序
/**思路: * 1. 依次比较相邻的元素,如果第一个比第二个大,就交换他们两个的位置 * 2. 对每一对相邻元素作同样的操作,从开始第一对到结尾的最后一对. 在这一点,最后的元素应该会是最大的数 * 3. 针对所有的元素重复以上的步骤,除了最后n个【n代表比较相邻元素的循环次数,如第一次循环比较结束出去最后一个元素n=1】 * 4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较 */ public static int[] bubbleSort(int[] arr) { //对数组进行非空及是否有元素判断 if(arr==null || arr.length==0) { return arr; } //每次循环都去掉最后面的i-1个元素,i代表循环次数 for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length - i - 1; j++) { //如果相邻的两个元素,前一个比后一个大则进行交换位置 if(arr[j]>arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr; }
4. 插入排序
/**思路: * 1. 认为第一个元素是排好序的,从第二个开始遍历 * 2. 拿当前的元素,从排好序的序列从中后往前找 * 3. 如果序列中的元素比当前元素大,就把它后移,直到找到一个小的 * 4. 将当前元素放在这个小的后面 */ public static int[] insertionSort(int[] arr) { //对数组进行非空及是否有元素判断 if(arr==null || arr.length==0) { return arr; } for (int i = 0; i < arr.length; i++) { for (int j = i; j > 0; j--) { //相邻两个元素比较,如果前一个大于后一个则交换二者的位置 if(arr[j] < arr[j-1]) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } return arr; }
5. 希尔排序
/**思路: * 1. 先取一个正整数d1(d1 < n),把全部记录分成d1个组,所有元素之间距离为d1的倍数的记录看成一组,然后在各组内进行插入排序 * 2. 然后取d2(d2 < d1) * 3. 重复上述分组和排序操作,直到取di = 1(i >= 1)位置,即所有记录成为一个组,最后对这个组进行插入排序. * * 一般选d1约为n/2,d2为d1/2,d3为d2/2 ... di = 1,n为数组元素个数 * * 根据需求,如果你想要结果从大到小排列,它会首先将数组进行分组,然后将较大值移到前面,较小值移到后面,最后将整个数组进行插入排序,这样比起一开始就用插入排序减少了数据交换和移动的次数,可以说希尔排序是加强版的插入排序 * 拿数组5,2,8,9,1,3,4来说,数组长度为7,当increment为3时,数组分为两个序列5、2、8和9、1、3、4,第一次排序,9和5比较,1和2比较,3和8比较,4和比其下标值小increment的数组值相比较 * * 此例子是按照从大到小排列,所以大的会排在前面,第一次排序后数组为9、2、8、5、1、3、4 * 第一次后increment的值变为3/2=1,此时对数组进行插入排序,实现数组从大到小排 */ public static int[] shellSort(int[] arr) { //对数组进行非空及是否有元素判断 if(arr==null || arr.length==0) { return arr; } for (int gap = arr.length/2; gap > 0 ; gap/=2) { for (int i = gap; i < arr.length; i++) { int j = i; while (j-gap>=0 && arr[j]<arr[j-gap]) { int temp = arr[j]; arr[j] = arr[j-gap]; arr[j-gap] = temp; j -= gap; } } } return arr; }
6. 大顶堆排序
/**思路: * 1. 将待排序的序列构建成一个大顶堆 * 2. 堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束 * * 最大堆调整: 将堆的末端子节点作调整,使得子节点永远小于父节点 * 创建最大堆: 将堆所有数据重新排序,使其成为最大堆 * 堆排序: 移除位于第一个数据的根节点,并做最大堆调整的递归运算 */ public static int[] heapSort(int[] arr) { for (int i = arr.length / 2; i >= 0; i--) { heapAdjust(arr,i,arr.length); }
//逐步将每个最大值的根节点与末尾元素交换,并且再调整二叉树,使其成为大顶堆 for (int i = arr.length - 1; i > 0; i--) {
//进行元素位置交换 swap(arr,i);
//交换之后,需要重新检查堆是否符合大顶堆,不符合则要调整 heapAdjust(arr,i); } return arr; }
/** 构建大顶堆 */ private static void heapAdjust(int[] arr,int i,int n) { int childLeaf; int fatherLeaf; for (fatherLeaf = arr[i]; leftLeafChild(i) < n; i = childLeaf) { childLeaf = leftLeafChild(i);
//如果左子树小于右子树,则需要比较右子树和父节点 if (childLeaf != n - 1 && arr[childLeaf] < arr[childLeaf + 1]) { //序号增1,指向右子树 childLeaf++; }
//父节点小于孩子结点时,进行交换 if (fatherLeaf < arr[childLeaf]) { arr[i] = arr[childLeaf]; } else { //大顶堆结构未被破坏,不需要调整 break; } } arr[i] = fatherLeaf; }
// 获取到左子结点 private static int leftLeafChild(int i) { return 2 * i + 1; }
private static void swap(int[] arr,int index1,int index2) { int tmp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = tmp; }
7. 归并排序
/*
* * 递归将一个较大的数组不断切分为较小的两个子数组,直到无法再切分之后再做合并,并在合并的过程中调整顺序 * 归并算法的难点是如何尽可能的减少额外存储空间的使用 */ public static int[] mergeSort(int[] arr) { if (arr == null || arr.length == 0) { return arr; }
//finalArr 作为辅助数组 int[] finalArr = new int[arr.length];
inMergeSort(arr,finalArr,arr.length - 1);
return finalArr; }
private static void inMergeSort(int[] arr1,int[] arr2,int high) { if (high <= low) { return; }
int middle = (low + high) / 2; //对左右子数组进行划分处理 inMergeSort(arr1,arr2,middle); inMergeSort(arr1,middle + 1,high);
//最终合并两个有序的子数组 finalMergeSort(arr1,middle,high);
}
private static void finalMergeSort(int[] arr1,int middle,int high) { int i = low; int j = middle + 1; int k = 0; while (i <= middle && j <= high) { if (arr1[i] <= arr1[j]) { arr2[k++] = arr1[i++]; } else { arr2[k++] = arr1[j++]; } } while (i <= middle) { arr2[k++] = arr1[i++]; } while (j <= high) { arr2[k++] = arr1[j++]; }
for (i = 0; i < k; ++i) { arr1[low + i] = arr2[i]; } }
关注微信公众号:大数据学习与分享,获取更对技术干货
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|