JAvaデータ構造学習の(二)簡単なソート
9016 ワード
泡のソートが最も古典的:
public void BubbleSort1(){
バブルソートの改良されたバージョンは、次のとおりです.
このうちBubbleSort 2は比較の回数を減らし、効率を高めた.3,4の2つの方法も同様の原理で、できるはずの無駄を減らした.
次に、配列を移動する回数を減らすことで効率を向上させるソートを選択します.
最後にソートを選択します.このソートはバブルソートよりも2倍速く、ソートを選択するよりも速くなければなりません.逆ソートであれば、優位性がない可能性がありますが、基本的なソートであれば可能です.
このソートには、重複値を削除する機能も追加されています.
もう一つの実現は、上記のような効率が高くないような気がします
効率が第一に高い環境がないのは逆順の場合で、この環境では移動回数が多いため、もともと別々に移動するのは一度に移動するのが速くない.その他の場合は差が少ない.
以下にすべてのコードを貼り付けます
public void BubbleSort1(){
for (int i = nElement - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]){
swap(j,j+1);
}
}
}
}
private void swap(int a,int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}バブルソートの改良されたバージョンは、次のとおりです.
/**（ ）
*
* ps: ， 。 ， n / 2， 。
*/
public void BubbleSort2(){
int i,j,k,left = 0,right = nElement - 1;
for (i = nElement/2; i > 0; i--) {
for (j = left; j < right; j++) {
if(arr[j] > arr[j+1]){
swap(j,j+1);
}
}
for (k = right - 1; k > left; k--) {
if(arr[k] < arr[k - 1] ){
swap(k,k - 1);
}
}
left++;
right--;
}
}
/**（ ）
* ps: ， ， 。
*/
public void BubbleSort3(){
boolean isSorted = false;
for (int i = nElement - 1; i > 0 && !isSorted; i--) {
isSorted = true;//
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j + 1]){
swap(j,j + 1);
isSorted = false;
}
}
}
}
/**（ ）
* ps: ， ， 。
*/
public void BubbleSort4(){
int lastIndex = nElement - 1,j=0;
while(lastIndex > 0){
for (int i = j = 0; i < lastIndex; i++) {
if(arr[i] > arr[i + 1]){
swap(i, i+1);
j = i;
}
}
lastIndex = j;
}
}このうちBubbleSort 2は比較の回数を減らし、効率を高めた.3,4の2つの方法も同様の原理で、できるはずの無駄を減らした.
次に、配列を移動する回数を減らすことで効率を向上させるソートを選択します.
public void selectSort() {
for (int i = 0; i < nElement - 1; i++) {
int k = i;
for (int j = i + 1; j < nElement; j++) {
if (arr[k] > arr[j]) {
k = j;
}
}
if (k != i) {
swap(k, i);
}
}
}最後にソートを選択します.このソートはバブルソートよりも2倍速く、ソートを選択するよりも速くなければなりません.逆ソートであれば、優位性がない可能性がありますが、基本的なソートであれば可能です.
public void insertSort(){
int repeat = 0,t = 0;
for (int i = 1; i < nElement; i++) {
int j = i;
while (j > t && arr[i] <= arr[j - 1]){
// -1
if(arr[i]==arr[j - 1]){
arr[i] = -1;
repeat++;
}
--j;
}
t = repeat;
if(j < i){
int temp = arr[i];
for (int k = i; k > j; k--) {
arr[k] = arr[k - 1];
}
arr[j] = temp;
}
}
if(repeat > 0){
nElement = nElement - repeat;
for (int i = 0; i < nElement; i++) {
arr[i] = arr[i + repeat];
}
}
}このソートには、重複値を削除する機能も追加されています.
もう一つの実現は、上記のような効率が高くないような気がします
public void insertSort2(){
for (int i = 1; i < nElement; i++) {
int j = i;
int temp = arr[i];
while(j > 0 && temp < arr[j - 1]){
arr[j] = arr[--j];
}
arr[j] = temp;
}
}効率が第一に高い環境がないのは逆順の場合で、この環境では移動回数が多いため、もともと別々に移動するのは一度に移動するのが速くない.その他の場合は差が少ない.
以下にすべてのコードを貼り付けます
package sort;
public class Sort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Sort o = new Sort(10000);
for (int i = 10; i > 0; i--) {
o.insert(i);
}
o.insert(9);
o.insert(8);
/*for (int i = 0; i < 10000; i++) {
o.insert(i);
}*/
long begin = System.currentTimeMillis();
o.insertSort();
long end = System.currentTimeMillis();
System.out.println("time="+(end - begin));
o.display();
}
private int[] arr = null;
private int nElement = 0;//
public Sort(int size){
this.arr = new int[size];
this.nElement = 0;
}
public int[] getArr(){return this.arr;}
/**
* @param c
*/
public void insert(int c){
arr[nElement++] = c;
}
public void BubbleSort1(){
for (int i = nElement - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]){
swap(j,j+1);
}
}
}
}
/**（ ）
*
* ps: ， 。 ， n / 2， 。
*/
public void BubbleSort2(){
int i,j,k,left = 0,right = nElement - 1;
for (i = nElement/2; i > 0; i--) {
for (j = left; j < right; j++) {
if(arr[j] > arr[j+1]){
swap(j,j+1);
}
}
for (k = right - 1; k > left; k--) {
if(arr[k] < arr[k - 1] ){
swap(k,k - 1);
}
}
left++;
right--;
}
}
/**（ ）
* ps: ， ， 。
*/
public void BubbleSort3(){
boolean isSorted = false;
for (int i = nElement - 1; i > 0 && !isSorted; i--) {
isSorted = true;//
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j + 1]){
swap(j,j + 1);
isSorted = false;
}
}
}
}
/**（ ）
* ps: ， ， 。
*/
public void BubbleSort4(){
int lastIndex = nElement - 1,j=0;
while(lastIndex > 0){
for (int i = j = 0; i < lastIndex; i++) {
if(arr[i] > arr[i + 1]){
swap(i, i+1);
j = i;
}
}
lastIndex = j;
}
}
/**
*
* ， 。
*
*/
public void OddEvenSort(){
boolean isSorted = false;int i=0;
while(!isSorted){
i++;
isSorted = OddOrEventSort(0) || OddOrEventSort(1);
}
System.out.println(i);
}
private boolean OddOrEventSort(int i){
boolean isSorted = true;
for (int j = i; j < nElement - 1; j+=2) {
if(arr[j] > arr[j+1]){
swap(j, j+1);
isSorted = false;
}
}
return isSorted;
}
public void insertSort(){
int repeat = 0,t = 0;
for (int i = 1; i < nElement; i++) {
int j = i;
while (j > t && arr[i] <= arr[j - 1]){
// -1
if(arr[i]==arr[j - 1]){
arr[i] = -1;
repeat++;
}
--j;
}
t = repeat;
if(j < i){
int temp = arr[i];
for (int k = i; k > j; k--) {
arr[k] = arr[k - 1];
}
arr[j] = temp;
}
}
if(repeat > 0){
nElement = nElement - repeat;
for (int i = 0; i < nElement; i++) {
arr[i] = arr[i + repeat];
}
}
}
public void insertSort2(){
for (int i = 1; i < nElement; i++) {
int j = i;
int temp = arr[i];
while(j > 0 && temp < arr[j - 1]){
arr[j] = arr[--j];
}
arr[j] = temp;
}
}
public static void insertSort(int[] elements){
for(int i = 1;i <elements.length; i++){
int j = -1;
while(j <= i && elements[i] > elements[++j]);// element[i] ，
if(j < i){
// j ， elements[i] j
int temp = elements[i];
for(int k = i-1;k >= j;k--){
elements[k+1] = elements[k];
}
elements[j] = temp;
}
}
}
public void selectSort() {
for (int i = 0; i < nElement - 1; i++) {
int k = i;
for (int j = i + 1; j < nElement; j++) {
if (arr[k] > arr[j]) {
k = j;
}
}
if (k != i) {
swap(k, i);
}
}
}
public void display(){
for (int i = 0; i <nElement; i++) {
System.out.println(arr[i]);
}
}
private void swap(int a,int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
}