冒泡排序(从小到大排)
冒泡排序是指比如有n个数据,拿第一个数据与剩下的n-1个数据进行比较,当这个数据比相比较过程中某个数据小就把他们进行交换,这样循环第一次就会能将最大的数据放到最上面第二轮就会将第二大的数据放到第二的位置上.......,以此循环下去,
比如有六个数据,{1,4,6,23,2,5};
那么模拟一下比较的过程就是
0-1 1-2 2-3 3-4 4-5
0-1 1-2 2-3 3-4
0-1 1-2 2-3
0-1 1-2
0-1
代码实现:
int a[] = new int[] {1,4,6,23,2,5};
for(int i = 0;i<a.length-1;i++)
{
for(int j = 0;j<a.length-i-1;j++)
{
if(a[j]>a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
选择排序(从大到小排)
选择排序是指第一数与第二数比较,如果第一个数比第二数小则将第一个数与第二个数进行交换.依次再比较下面的数,这样一次循环能将i一个较大的数放到相应的位置上,所以外层需要循环n次
如果有六个数据{1,4,6,23,2,5}
则是
0-1 1-2 2-3 3-4 4-5
1-2 2-3 3-4 4-5
2-3 3-4 4-5
3-4 4-5
4-5
5
如果出现这种数据
{ 1,2,3,4,5,6 }
那么每次都要交换一次,效率很低,所以优化一下就是先将较小的数的下标记录下来当外层一次循环完再进行交换
第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换
public static void selectSort(int[]a)
{
int minIndex=0;
int temp=0;
if((a==null)||(a.length==0))
return;
for(int i=0;i<a.length-1;i++)
{
minIndex=i;//无序区的最小数据数组下标
for(intj=i+1;j<a.length;j++)
{
//在无序区中找到最小数据并保存其数组下标
if(a[j]<a[minIndex])
{
minIndex=j;
}
}
if(minIndex!=i)
{
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp=a[i];
a[i]=a[minIndex];
a[minIndex]=temp;
}
}
}
插入排序
插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
以下面5个无序的数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int j = i - 1;
int temp = pDataArray[i]; //记录要插入的数据
while (j >= 0 && pDataArray[j] > temp) //从后向前，找到比其小的数的位置
{
pDataArray[j+1] = pDataArray[j]; //向后挪动
j--;
}
if (j != i - 1) //存在比其小的数
pDataArray[j+1] = temp;
}
}
