java数据结构及算法三

现在的位置: 首页 > 综合 > 正文

java数据结构及算法三

2013年08月11日 ⁄ 综合 ⁄ 共 8334字 ⁄ 字号小中大 ⁄ 评论关闭

为什么要对数据排序？便于组织数据并且某些算法要求数据必须有序。本章主要介绍三类简单排序方法：冒泡，选择，插入算法。基本的操作是比较交换。

冒泡排序：

Listing 3.1 The bubbleSort.java Program
// bubbleSort.java
// demonstrates bubble sort
// to run this program: C>java BubbleSortApp
//-------------------------------------------------------------
-
class ArrayBub
{
private double[] a; // ref to array a
private int nElems; // number of data items
//-------------------------------------------------------------
-
public ArrayBub(int max) // constructor
{
a = new double[max]; // create the array
nElems = 0; // no items yet
}
//-------------------------------------------------------------
-
public void insert(double value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//-------------------------------------------------------------
-
public void display() // displays array contents
{
- 70 -
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//-------------------------------------------------------------
-
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop
(backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
//-------------------------------------------------------------
-
private void swap(int one, int two)
{
double temp = a[one];
a[one] = a[two];
a[two] = temp;
}
//-------------------------------------------------------------
-
} // end class ArrayBub
////////////////////////////////////////////////////////////////
class BubbleSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display them again
} // end main()
} // end class BubbleSortApp

冒泡排序效率：N*N: 两层嵌套循环，算法效率就是N*N;

选择排序：

// selectSort.java
// demonstrates selection sort
// to run this program: C>java SelectSortApp
//-------------------------------------------------------------
-
class ArraySel
{
private double[] a; // ref to array a
private int nElems; // number of data items
//-------------------------------------------------------------
-
public ArraySel(int max) // constructor
{
a = new double[max]; // create the array
nElems = 0; // no items yet
}
//-------------------------------------------------------------
-
public void insert(double value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//-------------------------------------------------------------
-
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//-------------------------------------------------------------
-
public void selectionSort()
{
int out, in, min;
for(out=0; out<nElems-1; out++) // outer loop
{
- 76 -
min = out; // minimum
for(in=out+1; in<nElems; in++) // inner loop
if(a[in] < a[min] ) // if min greater,
min = in; // we have a new min
swap(out, min); // swap them
} // end for(outer)
} // end selectionSort()
//-------------------------------------------------------------
-
private void swap(int one, int two)
{
double temp = a[one];
a[one] = a[two];
a[two] = temp;
}
//-------------------------------------------------------------
-
} // end class ArraySel
////////////////////////////////////////////////////////////////
class SelectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArraySel arr; // reference to array
arr = new ArraySel(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.selectionSort(); // selection-sort them
arr.display(); // display them again
} // end main()
} // end class SelectSortApp
//-------------------------------------------------------------
算法效率：N*N;

插入排序：基础而且重要的排序算法

部分有序，在一个标识的左侧数据是有序的。

Listing 3.3 The insertSort.java Program
// insertSort.java
// demonstrates insertion sort
- 81 -
// to run this program: C>java InsertSortApp
//-------------------------------------------------------------
-
class ArrayIns
{
private double[] a; // ref to array a
private int nElems; // number of data items
//-------------------------------------------------------------
-
public ArrayIns(int max) // constructor
{
a = new double[max]; // create the array
nElems = 0; // no items yet
}
//-------------------------------------------------------------
-
public void insert(double value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//-------------------------------------------------------------
-
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//-------------------------------------------------------------
-
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
double temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is
smaller,
{
a[in] = a[in-1]; // shift item right,
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//-------------------------------------------------------------
-
- 82 -
} // end class ArrayIns
////////////////////////////////////////////////////////////////
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
arr.display(); // display them again
} // end main()
} // end class InsertSortApp

算法效率：N*N

对象排序：

// objectSort.java
// demonstrates sorting objects (uses insertion sort)
// to run this program: C>java ObjectSortApp
////////////////////////////////////////////////////////////////
class Person
{
private String lastName;
private String firstName;
private int age;
//----------------------------------------------------------
-
public Person(String last, String first, int a)
{ // constructor
lastName = last;
firstName = first;
age = a;
}
//----------------------------------------------------------
-
public void displayPerson()
{
System.out.print(" Last name: " + lastName);
System.out.print(", First name: " + firstName);
System.out.println(", Age: " + age);
}
//----------------------------------------------------------
-
public String getLast() // get last name
{ return lastName; }
} // end class Person
////////////////////////////////////////////////////////////////
class ArrayInOb
{
private Person[] a; // ref to array a
private int nElems; // number of data items
- 85 -
//-------------------------------------------------------------
-
public ArrayInOb(int max) // constructor
{
a = new Person[max]; // create the array
nElems = 0; // no items yet
}
//-------------------------------------------------------------
-
// put person into array
public void insert(String last, String first, int age)
{
a[nElems] = new Person(last, first, age);
nElems++; // increment size
}
//-------------------------------------------------------------
-
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
a[j].displayPerson(); // display it
System.out.println("");
}
//-------------------------------------------------------------
-
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
Person temp = a[out]; // remove marked person
in = out; // start shifting at out
while(in>0 && // until smaller one
found,
a[in-1].getLast().compareTo(temp.getLast())>0)
{
a[in] = a[in-1]; // shift item to the right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//-------------------------------------------------------------
-
} // end class ArrayInOb
////////////////////////////////////////////////////////////////
- 86 -
class ObjectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayInOb arr; // reference to array
arr = new ArrayInOb(maxSize); // create the array
arr.insert("Evans", "Patty", 24);
arr.insert("Smith", "Doc", 59);
arr.insert("Smith", "Lorraine", 37);
arr.insert("Smith", "Paul", 37);
arr.insert("Yee", "Tom", 43);
arr.insert("Hashimoto", "Sato", 21);
arr.insert("Stimson", "Henry", 29);
arr.insert("Velasquez", "Jose", 72);
arr.insert("Vang", "Minh", 22);
arr.insert("Creswell", "Lucinda", 18);
System.out.println("Before sorting:");
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
System.out.println("After sorting:");
arr.display(); // display them again
} // end main()
} // end class ObjectSortApp

简单排序的比较：

冒泡适合小数据量排序；选择排序多比较少交换，适合数据量少且相对于比较数据，交换更耗时的情况；

插入排序是三个简单排序中最有效的一个。

【上篇】Oracle SQL语句优化技术：解读实战技巧
【下篇】C中文件操作相关函数

作者: galanz

该日志由 galanz 于11年前发表在综合分类下，最后更新于 2013年08月11日.
转载请注明: java数据结构及算法三 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

java数据结构及算法三

作者: galanz

书签

最新文章New

本站推荐

返回首页