交换类排序:根据序列中两个元素关键字的比较结果来交换他俩在序列中的位置。冒泡排序:假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即A[i-1]>A[i])则交换他们,直到序列比较完。我们称它为一趟冒泡,结果将最小的元素交换到待排序序列的第一个位置。下一趟冒泡时,前一趟确定的最小元素不再参与比较,待排序列减少一个元素,每趟冒泡的结果把序列中最小元素放到了序列的最终位置,……,这样最多...
简单选择排序: package cn.mdj.test;public class SelectSort {public static void sort(int array[]){int len = array.length;int temp; //临时变量int index; //最小元素索引for(int i=0;i<len;i++){index = i;//假设第一个元素最小for(int j=i+1;j<len;j++){//将当前的最小元素与后面元素比较,获取最小的元素if(array[j]<array[index]){index = j;//交换索引,索引永远指向最小的那个元素}} //与后面元素遍历完后,看是否需要...
两种方法都编译运行通过,可以当做排序类直接使用。折半插入排序:publicclass Sort1 {publicstaticvoid main(String[] args) {InsertSort sort = new InsertSort();sort.InsertSort();int[] arr = sort.getarr();System.out.println();System.out.println("排序之后:");for (int ar : arr) {System.out.print(ar + " ");}} }class InsertSort {int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 };int i,high,low,...
简介排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排...
归并排序也是基于分治思想的一种排序算法,是通过对两个或两个以上的有序序列合并来实现的,对两个序列合并的叫两路归并,对两个以上序列合并的叫多路归并。归并排序的时间复杂度也为O(N*logN)。下面来看一下两路归并的实现:基本思想:归并排序时先找出序列的中间元素把序列分解为两个子序列,对子序列重复这个过程直至把序列分解成为只包含单个元素的序列,然后把相邻的序列两两合并使之有序,重复两两合并直至合并成为一个序列归...
排序算法之冒泡排序一、初级的冒泡排序import java.util.Arrays;/** * * @title BubbleSort * @describe 冒泡排序 * @author 张富昌 * @date 2016年10月1日下午3:56:30 */public class BubbleSortLow { // 起泡排序是快速排序的基础,但是排序速度较慢。 // 基本思想:将序列中第 1 个元素与第 2 个元素进行比较,如前者大于后者,则两个元素交换位置,否则不交换; // 再将第 2 个元素与第 3 个元素进行比较,如前者...
在面试过程中,经常会涉及到一些算法问题,下面说介绍一下冒泡排序算法及优化.冒泡排序分为从大到小和从小到大两种排序方式,唯一区别在于两个数交换的条件不同,从大到小排序是前面的数比后面的小时交换,而从小到大排序是前面的数比后面的数大的时候交换. 假设有N个数据放在数组nums中,现将数组nums中的N个数据从小到大进行排序假设使用冒泡排序算法对5个整数{8,3,-2,7,6}进行从小到大的排序冒泡排序的基本思想:在a[0] 到a[n-1]的...
堆的概念: 最小值堆:最小值堆是一个关键码序列{K0,K1,…Kn-1},它具有如下特性: Ki≤K2i+1 (i=0,1,…, n/2-1)Ki≤K2i十2 最大值堆:最大值堆是一个关键码序列{K0,K1,…Kn-1},它具有如下特性:Ki≥K2i+1 (i=0,1,…, n/2-1) Ki≥K2i十2 一句话,堆就是具有下列性质的二叉树:树的每个节点的值都大于等于其左右孩子节点的值就是大顶堆;树的每个节点的值都小于等于其左右孩子节点的值就是小顶堆。本文主要是想通过堆来...
#include <stdio.h> void sort(int list[], int low, int high, int &k, int end) {int x = list[low];while (low < high){while (low < high){if (list[high] >= x)high--;else{list[low] = list[high];break;}}while (low < high){if (list[low] <= x)low++;else{list[high] = list[low];break;}}for (int i = 0; i <= end; i++){printf("%d ", list[i]);}printf("\n");}list[low] = x;k = low; }void quickSort(int list[], int...
和在VC++6.0里相比 在OC里面实现 不算困难 可是我用惯了C/C++呢 快速排序,冒泡排序,直接插入排序和折半插入排序,希尔排序,堆排序,直接选择排序 /*******************************快速排序 start**********************************///随即取 当前取第一个,首先找到第一个的位置,然后分成left和right两组子集 ,分别对left和right继续执行分割(同上操作)-(void)QuickSort:(NSMutableArray *)list StartIndex:(NSInteger)st...
1publicclass BubbleSort {2publicint[] bubbleSort(int[] arr, int n){3int temp = 0;4 5for (int i=0; i<n-1; i++){6for (int j=0; j<n-1; j++){7if (arr[j] > arr[j+1]){8 temp = arr[j];9 arr[j] = arr[j+1]; 10 arr[j+1] = temp; 11 } 12 } 13 } 14return arr; 15 } 1617publicstaticvoid main(String[] args){ 18int[] a...
以下程序均将数据封装于DataWrap数据包装类中,如下所示: 1//数据包装类 2class DataWrap implements Comparable<DataWrap>3 {4int data;5 String flag;6public DataWrap(int data,String flag)7 {8this.data = data;9this.flag = flag; 10 } 11//重写compareTo方法12publicint compareTo(DataWrap other) 13 { 14returnthis.data > other.data ? 1 : (this.data == other.data ? 0 : -1); 15 ...
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并...
一.原理选择排序的原理非常简单,就是选出最小(大)的数放在第一位,在剩下的数中,选出最小(大)的数,放在第二位......重复上述步骤,直到最后一个数。二.过程原始数据第一次排序,选出最小的数1,交换1与25的位置第二次排序,选出剩下的数据中最小的数4,交换7与4的位置重复以上过程,最后三.代码#include <iostream> #include <vector>using namespace std;template <typename T> void SelectSort( vector<T> &nums ){int minInd...
冒泡排序思路:前后两两比较,如果前>后,则交换。每次从后向前扫描,所以每次扫描后最小的数就已经被交换到最前面了,需要扫描length次。时间复杂读O(n2)。稳定排序。稳定性,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。publicclass BubbleSort implements SortUtil.Sort{publicvoid sort(int[] data){for (int i = 0; i < data.length; i++ ){//遍历待排序的位 for (int j...