选择算法的实现
可以这样做：
public class Print {
public static void main(String[] args) {
int[] a = {4,7,1,3,9};
System.out.println("原来的：");
print(a);
selectionSort(a);
System.out.println("排序后：");
print(a);
}
//Java中数组是引用类型，所以在方法中操作数组可以改变它的内容
private static void selectionSort(int[] a) {
int k, temp;
for(int i=0; i<a.length; i++) {
k = i;//保护i,不能让i的值在下面比较时变了
for(int j=k+1; j<a.length; j++) {
if(a[j] < a[k]) {
k = j;
}
}
if(k != i) {
temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
}
private static void print(int[] a) {
for(int i=0; i<a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
② 用C++语言结构怎么实现在大量的数中快速选择的算法
先将数据读入到内存，然后进行排序，再用二分法查找，这样应该不会很慢。没有必要用多线程处理。
③ 题目1:一个简单的算法演示程序(JAVA语言实现)
1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。
④ 排序算法的实现与比较 编程实现直接插入排序、希尔、冒泡排序、快速、选择排序算法，并计算每种排序算法的
void BubbleSort(int Array[],int n)
{//输入数组进行冒泡排序
bool exchange=true;
for(int i=0;i<n;i++)
{
if(exchange==false)
return;
exchange=false;
for (int j=n-1;j>i;j--)
{
if(Array[j]<Array[j-1])
{
int temp=Array[j];
Array[j]=Array[j-1];
Array[j-1]=temp;
exchange=true;
}
}
}
}
void InsertSort(int Arrauy[],int n)
{//直接插入排序
for (int i=0;i<n-15 ;i++)
{
for (int j=i;j>=0;j--)
{
if (Arrauy[i+1]>Arrauy[j])
{//找到插入位置,在j之后
int temp=Arrauy[i+1];
for(int k=i;k>j;k--)
Arrauy[i]=Arrauy[i+1];
Arrauy[j+1]=temp;
break;
}
}
}
}
void BinaryInsertSort(int Arrary[],int n)
{//二分插入排序
for (int i=0;i<n-1;i++)
{
int temp=Arrary[i+1];
int left=0,right=i;
int mid=(left+right)/2;
while(left<right)
{
if(temp>Arrary[mid])
left=mid+1;
else
right=mid-1;
mid=(left+right)/2;
}
for(int j=i;j>mid;j--)
Arrary[j]=Arrary[j+1];
Arrary[mid+1]=temp;
}
}
void ShellSort(int Array[],int n)
{
//希尔插入排序
int gap=n;
do
{
gap=gap/3+1;
for (int i=gap;i<n;i++)
{//对子序列进行插入排序
int temp=Array[i];
int j=i-gap;
while(j>=0)
{
if (temp<Array[j])
{
Array[j+gap]=Array[j];
j=j-gap;
}
else
{
Array[j+gap]=temp;
break;
}
}
}
}while(gap>1);
}
void QuickSort(int Array[],const int n)
{//快速排序
QuickSort(Array,0,n-1);
}
void QuickSort(int Array[],const int left,const int right)
{//快速排序子过程
if(left<right)
{
int pivotpos= Partition(Array,left,right);
QuickSort(Array,left,pivotpos-1);
QuickSort(Array,pivotpos+1,right);
}
}
int Partition(int Array[],const int left,const int right)
{//划分过程
int pivot=left;
for (int i=left+1;i<=right;i++)
{
if(Array[i]<Array[left])
{
pivot++;
int temp=Array[i];Array[i]=Array[pivot];Array[pivot]=temp;
}
}
int temp=Array[left];Array[left]=Array[pivot];Array[pivot]=temp;
return pivot;
}
void SelectSort(int Array[],int n)
{
//直接选择排序
for (int i=0;i<n;i++)
{
int min=i;
for (int j=i;j<n;j++)
{
if(Array[j]<Array[min])
min=j;
}
if(min!=i)
{
int temp=Array[min];Array[min]=Array[i];Array[i]=temp;
}
}
}
时间复杂度 ：
插入，冒泡，选择 O（n×n）
快速O（nlogn）
希尔 不确定
⑤ 编写程序，实现三种排序算法（选择、插入、冒泡）
选择排序如下：
#include <stdio.h>
#include <stdlib.h>
void choose_sort( int array[], int s, int e );
int main( void )
{
int array[100];
int num;
int i;
int j;
int k;
printf( "input the amout(<100) of the array:" );
scanf( "%d", &num );
for( i = 0; i < num; i++)
{
scanf( "%d", array + i );
}
choose_sort( array, 0, num - 1 );
/*
for( i = 0; i < num - 1; i++ )
{
k = i;
for( j = i + 1; j < num; j++ )
{
k = array[j] < array[k] ? j : k;
}
if( i != k )
{
array[i] ^= array[k];
array[k] ^= array[i];
array[i] ^= array[k];
}
}
*/
printf( "the result of choose sort:\n" );
for( i = 0; i < num; i++)
{
printf( "%d ", array[i] );
}
printf( "\n" );
system( "pause" );
return 0;
}
void choose_sort( int array[], int s, int e )
{
int i;
int j;
int k;
for( i = s; i < e; i++ )
{
k = i;
for( j = i + 1; j <= e; j++ )
{
k = array[k] > array[j] ? j : k;
}
if( k != i )
{
array[i] ^= array[k];
array[k] ^= array[i];
array[i] ^= array[k];
}
}
}
插入排序如下：
#include <stdio.h>
#include <stdlib.h>
/*/already check */
void insert_sort( int array[], int s, int e );
int main( void )
{
int array[100];
int num;
int i;
int key;
int j;
printf( "input the amount(<100) of array: " );
scanf( "%d", &num );
for( i = 0; i < num; i++ )
{
scanf( "%d", array + i );
}
insert_sort( array, 0, num - 1 );
/*
for( i = 1; i < num; i++ )
{
key = array[i];
j = i - 1;
while( j >= 0 && array[j] > key )
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
*/
printf( "insert sort result:\n" );
for( i = 0; i < num; i++ )
{
printf( "%d ", array[i] );
}
printf( "\n" );
system( "pause" );
return 0;
}
void insert_sort( int array[], int s, int e )
{
int i;
int j;
int key;
for( i = s + 1; i <= e; i++)
{
key = array[i];
for( j = i - 1; j >= s && array[j] > key; j-- )
{
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
冒泡排序如下：
#include <stdio.h>
#include <stdlib.h>
void bubble_sort( int array[], int s, int e );
int main( void )
{
int i;
int num;
int array[100];
printf( "input amount(<100) of number: " );
scanf( "%d", &num );
for( i = 0; i < num; i++ )
{
scanf( "%d", array + i );
}
bubble_sort( array, 0, num - 1 );
printf( "result of bubble sort:\n" );
for( i = 0; i < num; i++ )
{
printf( "%d ", array[i] );
}
printf( "\n" );
system( "pause" );
return 0;
}
/*
void bubble_sort( int array[], int s, int e )
{
int i;
int j;
for( i = e; i > s; i-- )
{
for( j = s + 1; j <= i; j++ )
{
if( array[j - 1] > array[j] )
{
array[j] ^= array[j - 1];
array[j - 1]^= array[j];
array[j] ^= array[j - 1];
}
}
}
}
*/
注意：以上三个算法的main函数部分是为了让你输入一些数来测试排序算法而写的，排序的具体实现另写成一个函数。
补充题：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int search(char* str1, char* str2);
main()
{
char str1[100];
char str2[100];
int result;
printf("input first string: ");
scanf("%s", str1);
printf("input first string: ");
scanf("%s", str2);
result = search(str1, str2);
if(result < 0){
printf("str2 is not in str1.\n");
}
else{
printf("str2 is in str1, and begins at %d.\n", result);
}
system("pause");
}
int search(char* str1, char* str2){
int len1 = strlen(str1);
int len2 = strlen(str2);
int i;
int j;
int k;
i = 0;
while(i <= len1 - len2){
j = 0;
k = i;
while(j < len2 && str1[k] == str2[j]){
j++;
k++;
}
if(j == len2){
return i;
}
i++;
}
return -1;
}
注意：main也是测试用的，具体实现写成一个函数
⑥ 急！！！！！！求常用算法的实现与比较（直接选择、直接插入、冒泡）我要源程序哦，谢谢了
有点晕，这么几个算法。
请你看教科书。