黑马程序员技术交流社区

标题: 数组排序 [打印本页]

作者: kun1990 时间: 2013-12-9 23:28
标题: 数组排序
数组的选择排序是怎么的一回事，就是何为选择排序，怎么实现的？望请教...

作者: 雪飘舞 时间: 2013-12-9 23:41
本帖最后由雪飘舞于 2013-12-9 23:47 编辑

选择排序就是从数组零角标的值开始依次和后面的值进行比较，并按一定条件进行判断、互换，最终得到一个有序的数组
从小到大进行选择排序：
其实就是用数组零角标上的值依次和后面的值进行比较，如果零角标上的数值大于了后面的值，就用一个第三方变量的方法，将他们进行互换，否则继续比较下一个值，直到最后一个角标比较完毕。然后再从第二个角标开始（即大圈套小圈的原理）依次和后面的值进行比较。最终得到一个自小至大排列的数组
从大到小进行选择排序：
其实就是用数组零角标上的值依次和后面的值进行比较，如果零角标上的数值小于了后面的值，就用一个第三方变量的方法，将他们进行互换，否则继续比较下一个值，直到最后一个角标比较完毕。然后再从第二个角标开始（即大圈套小圈的原理）依次和后面的值进行比较。最终得到一个自大至小排列的数组

作者: 影凡 时间: 2013-12-9 23:42
选择排序的基本思想是将指定排序位置与其他数组元素分别对比，如果满足条件就交换元素位置，注意这里区别冒泡排序，不是交换相邻元素，而是把满足条件的元素与指定的排序位置交换（比如从第一个元素开始排序），这样排序好的位置逐渐扩大，最后整个数组都组成已排序好的格式。比如从1~10的乱序的数字堆（相当于数组）中分别选择合适的数字，组成从1到10的排序。首先从数组中选出1，放在第一位，然后选出2放在第二位（注意这时数组中已经没有1了），以此类推，直到找到9，放到8后面，最后只剩下10就不用选择了，直接放到最后就可以了。

作者: 高亮亮 时间: 2013-12-9 23:57
本帖最后由高亮亮于 2013-12-10 07:51 编辑

选择排序，其实可以这样理解，就是拿一个参照物，让数组中每一个元素和这个参照物进行比较。然后，每次都将两个中大的或者小的（取决于数组排序规则，从小到大还是从大到小）替换为下次的参照物。这样每完整循环一次，那么就能定下一个最值。下次比较就排除这个已经确定了的最值，重复之前的比较过程。
下面给你代码实现看看。

class ArrayDemo
{
public static void main(String[] args)
{//定义一个int型数组
int[] arr={2,4,1,5,23,5,4,674,34};
//建立外层for循环，拿出参照物(直接去数组中的第一个元素)遍历数组开始比较
for (int i=0;i<arr.length-1; i++)//这里因为第一个元素被拿出去当参照物，所以就从内循环从1开始遍历。
{//建立内层for循环，用参照物其余元素依次比较。
for (int j=i+1;j<arr.length;j++)
{
if (arr[j]>arr[i])
{
//如果arr[j]大于arr[j+1],就将两者元素数值互换，这样，循环结束后,留在数组左边的为最大值。
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}//遍历数组，查看排序结果。
for (int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
}
}

复制代码

作者: 剑魂 时间: 2013-12-10 00:15
选择排序实质是每次选择剩余元素最小或最大的出来，放在剩余元素的头或者尾的位置。假设第一个元素为最小的的情况，以后就是把剩余最小的找出来，放在第二，第三...依次排好。

class SelectSort
{
public static void main(String[] args)
{
int[] arr = {14,18,11,59,26};
show(arr);
for (int x = 0; x < arr.length-1 ; x++ )//把最小的往前排，每一个与后面元素相比，
//length-1是因为最后一个不用再比
{
for (int y = x+1; y < arr.length ;y++ )//x后的元素都一一与x比，找其中最小的与x交换
{
if(arr[x] > arr[y]){
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
System.out.println();
show(arr);
}
public static void show(int[] arr){
for(int x: arr){
System.out.print(x+" ");
}
}
}

复制代码

作者: 四五六七八 时间: 2013-12-10 00:23
E:\qwe.npg

作者: 四五六七八 时间: 2013-12-10 00:24
E:\qwe.npg

qwe.png (56.48 KB, 下载次数: 39)

选择排序

作者: 走遍世界找寻你 时间: 2013-12-10 14:06
本帖最后由走遍世界找寻你于 2013-12-10 15:12 编辑

一组数为39,34,54,47,59,97,68
选择排序其实实现方式是:
1.第一个数和后边的每个数都比较一次，条件满足交换位置，这样最小的数34就会被放到最后，第一轮比较结束就把这个数的位置给定下了。2.此时数组的第一个数和除了最后一位的其他所有数比较，条件满足交换位置，39被放到倒数第二位，第二轮结束第二个小的数位这也被定下了。3.此时数组的第一个数和除了最后两位的所有数比较，条件满足交换位置，第三小的数位置也被定下来了。4.以此类推直到最后，所有数的位置就确定了。外循环控制比较轮数，内循环控制数的比较次数。实现代码如下：
package HeiMa;

public class Demo3 {
public static void main(String[] args) {
int[] arr = {39,34,54,47,59,97,68};
selectSort(arr);
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + ",");
}

}
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr < arr[j]) {
int temp = arr;
arr = arr[j];
arr[j] = temp;
}
}
}
}
}

作者: 笑脸不在 时间: 2013-12-10 15:55
本帖最后由笑脸不在于 2013-12-10 16:23 编辑

为楼主服务~~特提供了选择排序和冒泡排序思路和代码，以示区别；代码仅供参考
1、选择排序：
1.1、需求：使用选择排序将数组 int[]  a={1,9,5,7,3} 按从小到大的顺序排列
1.2、选择排序思路：
      1、选取数组中的第一个（或最后一个数)a[0]
      2、将a[0]和数组中位于a[0]后面的数a[x]逐个比较：若a[0]>a[x],则交换a[0]和a[x]的值；这样当a[0]和数组中的最后一个数比较完后，就把数组中的最小值提取到a[0]位置存储起来了；这一步可以用一个for循环来实现
      3、然后将a[1]和数组中位于a[1]后的数a[x]逐个比较，若a[1]>a[x],则交换a[1]和a[x]的值；这个循环之后第二个最小值就提取出来并存储在了a[1]位置
      4、同理，当a[x]中的x倒了最后一个时就完成了这个选择排序
1.3、代码：
class Demo
{
      public static void main(String[] args) //主函数
      {
            int[] arr={1,9,5,7,3};
            selectionSort(arr);
            print(arr);
      }
      public static void selectionSort(int[] arr)//选择排序函数
      {
            for (int x=0;x<arr.length-1 ;x++ )
            {
                     for (int y=x+1;y<arr.length ;y++ )
                     {
                              if(arr[x]>arr[y])
                                    swap(arr,x,y);
                     }
            }
      }
      private static void swap(int[] arr,int x,int y)//交换arr[]数组中的两个值
      {
            int temp;

            {
                     temp=arr[y];
                     arr[y]=arr[x];
                     arr[x]=temp;
            }
      }
      public static void print(int[] arr)//打印arr[]数组的值
      {
            System.out.print("[");
            for (int x=0;x<arr.length ;x++ )
            {
                     if(x!=arr.length-1)
                              System.out.print(arr[x]+",");
                     else
                              System.out.println(arr[x]+"]");
            }
      }
}2.冒泡排序
2.1、需求：使用冒泡排序将数组 int[]  a={1,9,5,7,3} 按从小到大的顺序排列
2.2、选择排序思路：
      1、选取数组中的第一个（或最后一个数)a[0]
      2、将a[0]和a[1]比较若a[0]>a[1],则交换a[0]和a[1]的值；否则不交换。
            继续将a[1]和a[2]比较若a[1]>a[2],则交换a[1]和a[2]的值；
            .......
            将a[x]和a[x+1]比较，若是a[x]>a[x+1],则交换a[x]和a[x+1]的值；
            ......
         当x=arr.length-2时，遍历结束，这数组的最大值就存储到数组a的最后一个位置了
      3、将a[0]和a[1]比较若a[0]>a[1],则交换a[0]和a[1]的值；
            继续将a[1]和a[2]比较若a[1]>a[2],则交换a[1]和a[2]的值；
            .......
            将a[x]和a[x+1]比较，若是a[x]>a[x+1],则交换a[x]和a[x+1]的值；
            ......
         当x=arr.length-3时，遍历结束，数组的第二大值就存储在数组a的倒数第二个了
      4、最后当所有遍历完成时，数组的冒泡排序就完成了
2.3、代码：
class Demo1
{
public static void main(String[] args) //主函数
{
int[] arr={1,9,5,7,3};
bubbleSort(arr);
print(arr);
}
public static void bubbleSort(int[] arr)//冒泡排序函数
{
for (int x=arr.length-1;x>=0 ;x-- )
{
for (int y=0;y<x;y++ )
{
if(arr[y]>arr[y+1])
swap(arr,y,y+1);
}
}
}
private static void swap(int[] arr,int x,int y)//交换arr[]数组中的两个值
{
int temp;

{
temp=arr[y];
arr[y]=arr[x];
arr[x]=temp;
}
}
public static void print(int[] arr)//打印arr[]数组的值
{
System.out.print("[");
for (int x=0;x<arr.length ;x++ )
{
if(x!=arr.length-1)
System.out.print(arr[x]+",");
else
System.out.println(arr[x]+"]");
}
}
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2